Dijkstra算法中不能有负权重环的问题

Question

bobo老师，对于dijkstra算法中不能有负权重边的问题，可不可以理解为主要为了防止加权有向图中出现负权重环的情况，假设如果能保证环都是正权重的或0权重的，是不是在dijsktra算法中负权重边也是允许出现的呢？

Answer 1

liuyubobobo 2018-03-14 19:07:59

不完全。可以尝试下面的例子：寻找从0出发到1的最短路径，Dijkstra将得到错误的结果，而这个图中不存在环。

0->1 weight:3

0->2 weight:10

2->1 weight:-9

• 提问者 YoooooooA #1

  bobo老师，通过顶点的松弛，这个例子的最后的结果应该是1呀

• liuyubobobo 回复 提问者 YoooooooA #2

  dij算法每次找所有可到的顶点的距离最小值，然后就会固定下来这个最小值就是对应从src到这个顶点的最短距离。最终找到0->1的最短路径是3。用程序跑一下试试看?