Bellman-Ford 算法以解决具有附加边权重的任意连通图 G(V,E) 的单源最短路径问题 (SSSSPP) 而闻名，只要存在。
算法的基本实现版本，例如:Bellman-Ford-Wiki-page 及其 proof of correctness，根据我的理解，当使用所有边的平行松弛时，意味着一个有趣的副产品，我称之为“中间最优性属性”，(这可能对某些应用程序非常有帮助，例如 this question )如下所示:
After k iterations, we have every node identified with its shortest path from the same source, under the constraint of #edges in the path is <= k
在简单的最短路径存在的假设下，这将确保为 每个 目标节点生成 SSSPP 的最短路径解决方案，至多 |V|-1 次迭代。
以上属性是否正确？
根据某些人的说法(例如 this question 下方的评论)，这是不正确的，我不明白为什么!!
(更新:我在所有顶点上使用并行更新。)
最佳答案
假设我们有一个简单的图 A->B->C->D，所有权重都等于 1。
如果我们按 A、B、C、D 的顺序访问顶点，那么在第一次迭代期间我们将放宽以下所有条件:
A->B, finds shortest path to B is 1
B->C, finds shortest path to C is 2
C->D, finds shortest path to D is 3.
所以在第一次迭代中我们找到了到 D 的最短路径，尽管这条路径需要 3 条边。
但是，如果按照 D、C、B、A 的顺序访问顶点，则需要更多的迭代才能找到到 D 的最短路径。
换句话说，在 k 次迭代之后，我们肯定会找到#edges <= k 的任何最短路径，但是我们也可能找到使用更多边的更好路线。
关于algorithm - Bellman-Ford 算法的中间最优性，是否正确？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25813989/