已知最长路径长度时，是否需执行Bellman-Ford算法N-1次？

结论：只需要执行5次松弛操作即可确定所有最短路径，无需执行9次。

核心逻辑 #

Bellman-Ford算法的本质是通过逐轮松弛，逐步找到边数递增的最短路径：

• 第1轮松弛能确定所有边数为1的最短路径；
• 第k轮松弛能确定所有边数不超过k的最短路径。

题目中明确从源点S出发的最长路径边数为5，这意味着所有可达顶点的最短路径的边数必然≤5（因为最短路径不可能包含环，否则去掉环会得到更短的路径，边数更少）。因此第5轮松弛完成后，所有顶点的最短路径距离都已不再变化，后续的松弛操作不会产生任何更新。

极端情况说明 #

• 这里的“最长路径长度”必须指边的数量：如果是指路径的权重和，结论不成立。比如可能存在权重和很大但边数仅2的路径，同时存在边数6但权重和更小的最短路径，这种情况下5次松弛就不够。但考试场景中，“路径长度”默认指边数，符合题目语境。
• 需排除负权环：如果图中存在从S可达的负权环，那么不存在最短路径（路径长度可无限减小），此时无论执行多少次松弛都无法确定最短路径。但题目问的是“确定已找到最短路径”的场景，默认图中无此类负权环。

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