algorithm - 关于dijkstra算法的困惑？

Question

根据算法书Corman，Dijkstra 仅适用于所有边都具有非负权重的图。这是否意味着，如果有任何负权重的边将不适用于整个图形？或者它不会计算负重量边缘吗？请指出哪一个是对的？

score 7 · Accepted Answer

Dijkstra 算法有时可以处理一些负边的图，例如：

A-->B-->C

而w(A, B) = -1和w(B, C) = -2。

但是当至少有一个负边缘时，它不能证明总是正确的。喜欢：

A-->B-->C-->D
 \         /
  \ _____ /

其中w(A, B) = 1, w(B, C) = 3, w(C, D) = -5, w(A, D) = 2.

如果你选择 A 作为源点，你会得到从 A 到 D 的最短路径的长度是2Dijkstra 算法，-1实际上不是。

这是因为 Dijkstra 算法是一个贪心算法，它的正确性证明过程使用它的所有边都是非负的来获得矛盾。关于它的证明过程，你可以查看 Theorem 24.6 (Correctness of Dijkstra's algorithm)，Introduction to Algorithm。

score 0 · Accepted Answer

负边缘的主要问题是负循环。如果图在顶点 S 和顶点 T 之间包含负循环，则 S 和 T 之间不存在最短路径。Dijkstra 找到了最短路径，这是不正确的。

因此，负边缘不仅被忽略，而且会导致完全错误的解决方案。

另一种选择是 Bellman-Ford 算法，它在第 |V| 次迭代中找到那些负循环。

2 回答 2