我正在尝试了解 Bellman-Ford 算法，但我坚持正确性的证明。我使用过Wikipedia，但我根本无法理解证明。我在 Youtube 上没有找到任何有用的东西。希望你们中的任何人都可以简要解释一下。此页面“Bellman-ford 正确性我们可以做得更好”没有回答我的问题。
谢谢你。
问问题
777 次
1 回答
0
让我们从没有负循环的图的动态规划的角度来看问题。
我们可以将动态规划的记忆表可视化如下：
列代表节点，行代表更新步骤（节点 0 是源节点），从一个步骤中的一个框指向下一步中的另一个框的箭头是min更新（步骤 0 是初始化）。
我们从所有最短路径中选择一条路径并说明它为什么是正确的。让我们选择 0 -> 3 -> 2 -> 4 -> 5。这是从 0 到 5 的最短路径，否则我们可以选择任何其他路径。我们可以通过归约来证明正确性。初始为源0，显然0与自身的距离应该为0，最短。我们假设 0 -> 3 -> 2 是 0 和 2 之间的最短路径，我们将在第三次迭代后证明 0 -> 3 -> 2 -> 4 是 0 和 4 之间的最短路径。
首先，我们证明在第三次迭代之后必须固定/收紧节点 4。如果节点 4 不固定，则意味着除了 0 -> 3 -> 2 -> 4 之外，至少有一条路径可以到达 4，并且该路径应该短于 0 -> 3 -> 2 -> 4，即与我们的假设相矛盾，即 0 -> 3 -> 2 -> 4 -> 5 是 0 和 5 之间的最短路径。那么在第三次迭代之后，应该连接 2 和 4。
其次，我们证明松弛应该是最短的。它不能越来越小，因为它是唯一最短的路径。
让我们看一个带有负循环的图表。
这是它的记忆表：
让我们证明在 |V| 的迭代中，这里 |V| 是顶点数 6，更新不应该停止。
我们假设更新停止（并且存在负循环）。让我们看看循环 3 -> 2 -> 4 -> 5 -> 3。
dist(2) <= dist(3) + w(3, 2)
dist(4) <= dist(2) + w(2, 4)
dist(5) <= dist(4) + w(4, 5 )
距离 (3) <= 距离 (5) + w(5, 3)
并且我们可以从上面的四个不等式中，将左边和右边相加，得到如下不等式：
dist(2) + dist(4) + dist(5) + dist(3) <= dist(3) + dist(2) + dist(4) + dist(5) + w(3, 2) + w( 2, 4) + w(4, 5) + w(5, 3)
我们减去两边的距离，得到：
w(3, 2) + w(2, 4) + w(4, 5) + w(5, 3) >= 0，这与我们的说法相矛盾 3 -> 2 -> 4 -> 5 -> 3 是负循环。
所以我们确信在 |V| 的步骤和之后的步骤更新将永远不会停止。
我的代码在Gist上。
参考：
于 2021-04-07T15:18:50.213 回答