Bellman-Ford算法第n次迭代能否100%检测到所有负环？

结论 #

是，只要负环是源点可达的，就100%会在第n次（n为图中顶点总数）迭代时出现两点间距离下降的情况。

原理说明 #

• Bellman-Ford算法的前n-1次迭代，本质是在枚举所有长度不超过n-1的简单路径的最短距离。因为没有环的简单路径最多经过所有n个顶点各1次，最多只有n-1条边，所以前n-1次迭代结束后，所有无环路径的最短距离已经完全收敛，不可能再被更短的无环路径更新。
• 如果图中存在源点可达的负环，那么沿着负环绕行任意次都能让路径总长度持续变小。第n次迭代时我们会尝试长度为n的路径，这类路径必然包含至少一个环，只要这个环是负环，计算出来的路径长度就会比前n-1次得到的最短距离更小，必然触发距离更新。

例外情况 #

如果负环和源点不在同一个连通分量，源点完全无法到达负环上的任意顶点，那么负环不会影响任何源点可达节点的最短距离，第n次迭代也不会出现距离下降。这种情况我们一般认为属于「不存在源点可达的负环」的范畴，不影响Bellman-Ford负环检测逻辑的正确性。

内容的提问来源于stack exchange，提问作者SNORLAX