1. 概述
Bellman-Ford 算法是一种非常流行的图算法，用于计算从一个节点到图中所有其他节点的最短路径。该算法特别适用于包含负权重边的图结构。
本文将深入探讨 Bellman-Ford 算法的原理、实现步骤、示例分析以及时间复杂度。我们还将解释为什么需要特别关注图中的负权重边。
2. 算法背景
Bellman-Ford 是一种单源最短路径（Single-Source Shortest Path）算法。与 Dijkstra 算法不同，它能处理图中存在负权重边的情况，因此在某些特定场景下更具优势。
✅ 优势：支持负权重边
❌ 缺点：时间复杂度高于 Dijkstra
3. 为什么需要关注负权重边？
在图论中，负权重边可能导致图中出现负权重环（Negative Cycle），这会使得最短路径无法确定。例如：
假设我们要从城市 M 到城市 R，路径中存在一个总权重为 -1 的环 NQP。如果我们不断绕这个环，总路径长度会无限减小，从而无法得出最短路径。
4. Bellman-Ford 算法步骤详解
算法伪代码如下：
algorithm BellmanFord(G, S, W):
// G: 有向图；S: 起始顶点；W: 边权重
D <- 距离数组，初始化为无穷大
D[S] <- 0
for i from 1 to |V| - 1:
for each edge (u, v) in E:
if D[v] > D[u] + W[u, v]:
D[v] = D[u] + W[u, v]
for each edge (u, v) in E:
if D[v] > D[u] + W[u, v]:
print("图中存在负权重环")
算法流程说明：
- 初始化距离数组 D：除起点外所有节点距离设为无穷大。
- 松弛所有边 |V| - 1 次：逐步更新最短路径。
- 检查负权重环：若还能继续松弛，说明存在负环。
算法特点：
- 属于动态规划范畴
- 使用自底向上（Bottom-Up）策略
- 可检测负权重环
5. 示例分析
5.1. 无负权重环的图
假设起点为 S：
- 初始化后：S 距离为 0，其余为 ∞
- 经过 5 次迭代后，所有最短路径被确定
- 第 6 次检查无更新，说明无负环
示例中部分关键松弛过程如下：
- S → A：∞ → 10
- A → B：∞ → 12
- D → A：10 → 5
- C → B：10 → 5
最终结果如下图所示：
5.2. 含负权重环的图
算法运行后：
- 前 3 次迭代不断更新节点距离
- 第 4 次检查时发现 D 的距离仍可更新 ⇒ 存在负环
结论：图中存在负权重环，无法确定最短路径。
6. 时间复杂度分析
| 步骤 | 时间复杂度 |
|---|---|
| 初始化 | O(V) |
| 松弛边 | O(V * E) |
| 检查负环 | O(E) |
总体时间复杂度为：O(V * E)
⚠️ 注意：对于稠密图（E ≈ V²），复杂度较高，建议使用 Dijkstra；但对于稀疏图（E ≈ V），Bellman-Ford 表现尚可。
7. 总结
- Bellman-Ford 是一种支持负权重边的单源最短路径算法
- 可用于检测图中是否存在负权重环
- 时间复杂度为 O(V * E)，适用于稀疏图
- 实现简单，适合教学和特定应用场景
如需处理负权重边或检测负环，Bellman-Ford 是一个非常实用的选择。