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

来源：9-3 实现Dijkstra算法

YoooooooA

2018-03-14

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

写回答

1回答

liuyubobobo

2018-03-14

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

0->1 weight:3

0->2 weight:10

2->1 weight:-9

liuyubobobo

YoooooooA

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

2018-03-15

共2条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 4

回答 1

回答 1

回答 2

回答 1