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来跑?如果可以则时间复杂度的变化是变快还是变慢
感谢解答