Bellman-Ford算法最坏场景示例求解：需V-1次边遍历的情况

Bellman-Ford算法的迭代逻辑是每次遍历所有边时，只能基于上一轮迭代得到的最短距离，松弛下一层节点的路径。如果最短路径的结构是一条包含 V-1 条边的线性链（也就是从源点到最远节点的最短路径要经过所有其他节点），就必须跑满 V-1 次迭代才能让所有节点的最短距离收敛到正确值。

具体示例（V=4，需3次迭代） #

我们构造一个无负权环的线性图：

• 节点：源点 s、A、B、C
• 边及权重：s→A（2）、A→B（3）、B→C（1）
• 初始距离设定：dist[s] = 0，其余节点距离为 ∞

迭代过程：

1. 第1次遍历所有边：
   只能松弛 s→A，更新 dist[A] = 0 + 2 = 2；B 和 C 的距离仍为 ∞。
2. 第2次遍历所有边：
   基于 A 的新距离，松弛 A→B，更新 dist[B] = 2 + 3 = 5；C 的距离还是 ∞。
3. 第3次遍历所有边：
   基于 B 的新距离，松弛 B→C，更新 dist[C] = 5 + 1 = 6。

此时所有节点的最短距离才全部计算完成——少一次迭代都无法得到 C 的正确最短路径。

为什么这是最坏情况？ #

这种线性链结构下，最短路径的信息只能从源点“逐步传递”到后续节点，每一轮迭代最多能把距离信息往前推一个节点。没有任何边能让算法提前跳过中间节点直接更新更远节点的距离，因此必须执行满 V-1 次边遍历，对应时间复杂度的最坏情况 O(V*E)。

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