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來跑?如果可以則時間複雜度的變化是變快還是變慢
感謝解答