作者DJWS (...)
看板Prob_Solve
标题Re: [问题] Gabow's scaling algorithm for SSSP
时间Mon Aug 10 13:54:25 2009
1F：→ LPH66:是说如果把这个概念放回Dijstra去如何? 被relax的人如果不在 08/10 05:34
2F：→ LPH66:heap当中 (这可以设flag) 就重新enheap... 08/10 05:34
3F：→ LPH66:这样能不能把Dijkstra改成可处理负边? 08/10 05:36
当然可以罗，经过修正之後，
这整件事就变成了SPFA，只是容器从queue变成了heap而已。
更进一步来说，这个修正，其实是把整个演算法
由label setting改成label correcting，并没有什麽特别的。
有负边的情况下，label setting的演算法本来就会失效，
而不得不用label correcting的演算法。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.137.83.14