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

Question

已关闭。这个问题是 off-topic 。目前不接受答案。

---

想要改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。

已关闭10 年前。

Improve this question

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

感谢您的帮助

Answer 1

贝尔曼-福特算法查找加权图中从源顶点到所有其他顶点的最短路径。

负权重循环的问题是不存在最短路径。

在不绘制的情况下，考虑4个节点的情况，其中A是源，节点B、C、D是其他顶点。

所有边的权重如下:

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

贝尔曼-福特将得出以下最短路径长度

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 中检测负权重循环并不困难，因此这假设是一个简单的实现。