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

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

lidlesseye11

2020-10-09 00:17:20 +08:00

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

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

JasonLaw

2020-10-09 22:26:26 +08:00

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

lidlesseye11

2020-10-09 23:48:50 +08:00

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

JasonLaw

2020-10-10 06:47:15 +08:00 via iPhone

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

JasonLaw

2020-10-10 07:14:08 +08:00 via iPhone

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