Dijkstra算法为什么不能处理负权边
回答
Dijkstra 是贪心算法:每次从未确定的顶点中取当前距离最小的一个,把它的最短距离“定下来”。这一步成立的前提是所有边权 ≥ 0,因为之后再经别的顶点绕过来,路径长度只会增加、不会减少。出现负权边后,已确定的顶点仍可能被后续路径缩短,贪心结论失效。有负权边但无负环时可用 Bellman-Ford(O(VE));存在从源点可达的负环时最短路不存在(可以无限变小),Bellman-Ford 能检测出来。
例:s→a 权 2,s→b 权 5,b→a 权 -4。
- 从 s 出发,a 的距离 2 较小,先确定 d(a) = 2。
- 再确定 b,d(b) = 5;经 b 到 a 为 5 + (-4) = 1,但 a 已确定,不再更新。
- 算法输出 d(a) = 2,而真实最短路 s→b→a 长度是 1(已用程序复现这一错误)。
依据:严蔚敏《数据结构》「图」一章中的最短路径与 Dijkstra 算法。
相关官方导图:数据结构期末 · 图、查找与排序