下面是我所找到的一些资料：
但我还是不能够理解 Bellman–Ford 算法。
我又重新看了一遍MIT 6.006 Lecture 17: Bellman-Ford 中的正确性证明，终于算是明白了，希望也对后来看这个主题的人有所帮助。
 |
1
litmxs Oct 8, 2020 via Android
因为每次的松弛操作都可以保证从一个结点到其相邻结点的最短路估计值达到最短路的实际值，也就是保证了所有深度为 1 的路径最短。n 次操作则可以保证所有深度为 n 的路径最短。由于在不存在负圈的情况下，从 s 出发到任意结点的最短路不会经过同一个结点两次，所以最短路的长度（路径上边的数量）不会超过|v|-1 。所以算法可以在有限次数的松弛下结束。
|
 |
2
lidlesseye11 Oct 9, 2020
· 关于 V-1
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ 参考 How does this work? 那一段 ·"不变性（ invariant ）"是啥意思？ |
 |
3
JasonLaw OP @lidlesseye11 #2 我说的“不变性（ invariant ）”其实是 loop invariant -https://stackoverflow.com/questions/3221577/what-is-a-loop-invariant
|
|
4
lidlesseye11 Oct 9, 2020
@JasonLaw
受教了。 那 BF 的 loop invariant 应该就是 After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. 吧 |
|
5
JasonLaw OP @lidlesseye11 对，而且可以通过这个 loop invariant 证明算法的正确性。
|
Select Language