java - 如果存在负权重循环，贝尔曼-福特算法究竟会发生什么？

Question

我试图准确理解为什么贝尔曼-福特算法不适用于负重量循环。我明白负重循环会阻止程序给出正确的答案。但是，如果存在负重量循环，程序中究竟会发生什么？

谢谢你的帮助

Answer 1

Bellman-Ford 算法在加权图中找到从源顶点到所有其他顶点的最短路径。

负权循环的问题是没有最短路径。

不画图，考虑4个节点的情况，其中A为源，节点B,C,D为其他顶点。

所有边的权重如下：

w(A,B) = 1
w(B,C) = 1
w(C,D) = 1

Bellman-Ford 将得出以下最短路径长度

path(A~B) = 1
path(A~C) = 2
path(A~D) = 3

但是，如果我们添加一个创建负权重循环的边缘会怎样。例如从 C 到 B 的一条边，权重为 -2。

w(C,B) = -2

现在有一个负重循环。通过步行(B,C,B)，我们得到 -1 (1 + -2) 的总路径权重。

如果我们再次运行 Bellman-Ford，它会给我们提供它认为的从 A 到 D 的最短路径，就像以前一样。[注 1]

但这一次，就错了。

事实上，算法给我们的整数最短路径权重并不重要，因为我们总能找到一个更短的。

例如，假设算法给了我们原始路径权重 3 (A,B,C,D)。好吧，很容易看出我们可以构造一条更短的路径：(A,B,C,B,C,D)这给了我们 2 的路径权重。

但这也不是最短的路径。例如(A,B,C,B,C,B,C,D)给我们一个路径权重 1。

如您所见，我们可以通过在顶点 B 和 C 之间重复循环来构造任意短的路径权重。这只是因为我们的图包含负权重循环。

所以并不是贝尔曼-福特没有正确找到最短路径。
...更准确地说，没有最短路径。

[1] 在 Bellman-Ford 中检测负权重循环并不难，因此这是一个简单的实现。