为什么 Bellman–Ford 算法需要循环“顶点个数 - 1”次呢？

[JasonLaw]

下面是我所找到的一些资料：

• shortest path - Why do we need to run the bellman-ford algorithm for n-1 times? - Computer Science Stack Exchange
• graph - Why need (node number - 1) iterations in Bellman Ford algorithm to find shortest paths? - Stack Overflow

但我还是不能够理解 Bellman–Ford 算法。

• 为什么 Bellman–Ford 算法需要循环“顶点个数 - 1”次？
• 每次循环到底保证了什么不变性（ invariant ）？最后可以帮助证明，经过“顶点个数 - 1”次循环后，能够找到顶点 s 到其他顶点的最短距离。

我又重新看了一遍MIT 6.006 Lecture 17: Bellman-Ford 中的正确性证明，终于算是明白了，希望也对后来看这个主题的人有所帮助。

[litmxs]

因为每次的松弛操作都可以保证从一个结点到其相邻结点的最短路估计值达到最短路的实际值，也就是保证了所有深度为 1 的路径最短。n 次操作则可以保证所有深度为 n 的路径最短。由于在不存在负圈的情况下，从 s 出发到任意结点的最短路不会经过同一个结点两次，所以最短路的长度（路径上边的数量）不会超过|v|-1 。所以算法可以在有限次数的松弛下结束。

[lidlesseye11]

· 关于 V-1
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
参考 How does this work? 那一段

·"不变性（ invariant ）"是啥意思？

[JasonLaw]

@lidlesseye11 #2 我说的“不变性（ invariant ）”其实是 loop invariant -https://stackoverflow.com/questions/3221577/what-is-a-loop-invariant

[lidlesseye11]

@JasonLaw
受教了。
那 BF 的 loop invariant 应该就是 After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. 吧

[JasonLaw]

@lidlesseye11 对，而且可以通过这个 loop invariant 证明算法的正确性。

[JasonLaw]

@litmxs 感觉你说的“ 因为每次的松弛操作都可以保证从一个结点到其相邻结点的最短路估计值达到最短路的实际值，也就是保证了所有深度为 1 的路径最短。n 次操作则可以保证所有深度为 n 的路径最短。”怪怪的，但是我又说不太上来是哪里有问题，替换为“ After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated.”会更好理解。