作者wilson50101 (我觉得我还不错啊)
看板Grad-ProbAsk
标题[理工] 演算法DAG求最短路径
时间Wed Oct 17 11:10:10 2018
http://i.imgur.com/Ps4OwjH.jpg
图1是DAG找最短路径in linear time
利用先做topological sort 再做Bellman Ford
http://i.imgur.com/PMwfWZp.jpg
图2是Dijkstra Algo
http://i.imgur.com/I0L3V8h.jpg
图3是Bellman Ford Algo
想要问的是
1.为何图1的Algo 在Relax的时候
会和Dijkstra一样(如图2)是针对点作relax
演算法版本的Bellman Ford不是应该是对边做relax吗(如图3)？怎麽在DAG变得不一样了
2.如果DAG没有负边的话是否能把Bellman Ford换成Dijkstra来跑?如果可以则时间复杂度的变化是变快还是变慢
感谢解答
-----
Sent from JPTT on my Asus ASUS_Z016D.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.10.233.112
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1539745812.A.366.html
※ 编辑: wilson50101 (39.10.233.112), 10/17/2018 11:11:33
※ 编辑: wilson50101 (39.10.233.112), 10/17/2018 11:12:07