为何Bellman-Ford算法执行|V|-1轮迭代可保证找到最短路径？

先明确两个核心前提：

• 不含负权环的图中，最短路径一定是简单路径（路径里没有重复顶点）——如果有环，要么是正权环（绕环会增加路径长度，不可能是最短路径），要么是负权环（题目已排除这种情况）。
• 简单路径的边数最多是|V|-1条——毕竟|V|个顶点的简单路径，顶点不重复，边数必然比顶点数少1。

再看Bellman-Ford的核心操作：松弛边。对每条边u→v，检查是否能通过u的当前最短距离加上边的权重，得到v的更短距离，如果可以就更新v的距离。

每次遍历所有边的过程，本质是逐步覆盖不同长度的最短路径：

• 第1次遍历所有边：能算出所有最多包含1条边的最短路径（也就是直接相连顶点对的最短距离）。
• 第2次遍历所有边：基于第1次的结果，能算出所有最多包含2条边的最短路径（比如通过一个中转顶点的路径）。
• ...
• 第k次遍历所有边：能算出所有最多包含k条边的最短路径。

既然最短路径最多需要|V|-1条边，那遍历|V|-1次后，所有可能的最短路径（不管是1条边、2条边，还是最长的|V|-1条边的路径）都已经被松弛到了最优状态。之后再遍历边，也不会再更新任何顶点的距离值——因为已经没有更短的路径可以找到了。

举个直观的例子：假设图是一条直线链A→B→C→D→E（5个顶点，|V|-1=4）。

• 第1次遍历：得到A→B的最短距离（1条边）。
• 第2次遍历：通过A→B的结果，得到A→C的最短距离（2条边）。
• 第3次遍历：得到A→D的最短距离（3条边）。
• 第4次遍历：得到A→E的最短距离（4条边）。
  这时候所有顶点的最短距离都已确定，再遍历也不会有更新了。

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