有人可以告诉我为什么这个 dijkstra 算法的实现不适用于负权重吗？

Question

我查看了 dijkstra 算法 found here 的实现，但它似乎对负权重工作正常。

具体来说，relax 方法会更新顶点在优先级队列中的距离，或者如果它最初不在队列中，则将其重新插入。

并且由于没有任何检查来确保我们不会重新插入一个已知的顶点，这个实现是否更像是一个 bellman-ford 算法，我们不断插入顶点以访问和放松直到运行超出减少距离的边缘？

例如：

当运行在下图中以A为源时，我们首先确定以下距离：

C = 0
B = 1
D = 99

然后在我们的队列移除之后，我们剩下 (D, 99)，这让我们访问顶点 D 并放松它。当放宽顶点 D 时，我们发现 (D 到 B = -300)，这使得到 B 的距离为 -201。现在使用上面的 "relax" 方法，我们将 (B, -201) 重新插入到队列中。现在我们取队列的最小值，即我们刚刚插入的 (B, -201)。由此，我们放松 B，我们可以得到到 C 的距离为 -200。

我知道任何负循环都会使程序不终止，但是如果给我们一个没有负循环的图呢？希望我没有遗漏任何细节。感谢您的帮助！

Answer 1

因为如果你输入负权重，它会 throw new IllegalArgumentException("edge " + e + " has negative weight");

Answer 2

Dijkstra 基于这样的事实，即一旦访问了节点及其所有边 "used"，就再也不会访问它，因此复杂度很低（不需要 "re-balancing the whole graph"。）

这两个都是基于 non-negative 边，因为如果有负边，你必须 "re-balance" 它们并且复杂性会增加很多。正如你提到的，负循环的循环根本不会结束。

作者抛出异常的原因是他不想处理"not valid"图，尤其是无尽的循环。

PS：您的特定图实际上应该可以由 Dijkstra 求解，但想象一下这个图有负边且没有循环：

A ->(1) B ->(1) -> C
|      (-300)
v       ^
(5)     |
D ->(1) E

你真的解决了

B=1
C=2

然后关闭 A、B 和 C，不想再输入它们。但在这之后你会发现 A->D->E->B 是 -294 然后你有 re-enter 所有其他值。

想象一下为什么这么糟糕，我再举一个例子

    A ->(1) B ->(1) -> C -> SUPERGRAPH
    |    (-999999)
    v       ^
  (99999)   |
    D ->(1) E

所以现在 A->D 的值非常高，C 指向一些 SUPERGRAPH，但是 A 的总值 "length" 不超过 99999。

会发生什么？即使这行得通并且没有其他循环，您从 A 求解整个超图，但在那之后，您发现实际上 A->B 短得多，您必须再次求解整个 SUPERGRAPH。如果你有更多这样的情况，对于每一种情况，你都必须再次运行 Dijkstra 算法。

有人可以告诉我为什么这个 dijkstra 算法的实现不适用于负权重吗？

Can someone walk me through why this implementation of dijkstra's algo doesn't work for negative weights?

java

algorithm

dijkstra