→ LPH66:是說如果把這個概念放回Dijstra去如何? 被relax的人如果不在 08/10 05:34
→ LPH66:heap當中 (這可以設flag) 就重新enheap... 08/10 05:34
→ LPH66:這樣能不能把Dijkstra改成可處理負邊? 08/10 05:36
當然可以囉，經過修正之後，
這整件事就變成了SPFA，只是容器從queue變成了heap而已。
更進一步來說，這個修正，其實是把整個演算法
由label setting改成label correcting，並沒有什麼特別的。
有負邊的情況下，label setting的演算法本來就會失效，
而不得不用label correcting的演算法。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.83.14