贝尔曼-福特算法

#贝尔曼-福特算法

• 什么是贝尔曼-福特算法
• 操作步骤
• 负权边
• 时间复杂度

#什么是贝尔曼-福特算法

贝尔曼-福特（Bellman-Ford）算法用于在加权图中求解最短路径问题。它通过对所有边反复进行松弛操作，逐步逼近最短路径。

#操作步骤

以 A 为起点、G 为终点为例：

B --1-- E
|      |
9      5
|      |
A --6-- D --3-- G
|      |      |
2      2      4
|      |
C --9-- F

第 1 步：初始化——起点 A 的权重为 0，其他顶点为无穷大（∞）

A=0  B=∞  C=∞  D=∞  E=∞  F=∞  G=∞

第 2 步：遍历所有边，对每条边计算「顶点权重 + 边权重」，如果比目标顶点当前权重小就更新

选边 A-B: A 的权重 0 + 边权 9 = 9 < ∞ → 更新 B=9
选边 A-C: 0 + 2 = 2 < ∞ → 更新 C=2
选边 A-D: 0 + 6 = 6 < ∞ → 更新 D=6
选边 C-B: 2 + 9 = 11 > 9 → 不更新
选边 B-D: 9 + ... 
...（对所有边执行一轮）

第 3 步：重复第 2 步，直到所有顶点的权重不再更新

第1轮结束: A=0  B=8  C=2  D=4  E=9  F=10  G=14
第2轮结束: A=0  B=7  C=2  D=4  E=8  F=10  G=14
第3轮结束: 所有顶点都不再更新 → 结束

最终最短路径：A → C → D → F → G，权重为 14。

#负权边

贝尔曼-福特算法的最大优势是能处理负权边。

如果图中有一条负权边:
  A --4--> B --(-3)--> C

从 A 到 C: 4 + (-3) = 1，比直接 A → C 更短

但如果一个闭环的权重总和为负数，不断遍历这个闭环就能让路径权重无限减小，此时不存在最短路径。贝尔曼-福特算法可以通过检测「n 轮更新后是否还能继续更新」来判断这种情况。

#时间复杂度

#与狄克斯特拉算法的对比

#小结

• 贝尔曼-福特通过对所有边反复松弛来求最短路径
• 支持负权边（最大优势），能检测负权环
• 时间复杂度 O(nm)，比狄克斯特拉慢
• 存在负权边时用贝尔曼-福特，否则用更快的狄克斯特拉