[理工] 演算法DAG求最短路徑
圖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://www.ptt.cc/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