编辑“︁Bellman-Ford算法”︁

{{DISPLAYTITLE:Bellman-Ford算法}}
'''Bellman-Ford算法'''是一种用于求解单源最短路径问题的算法，适用于带有负权边的有向图或无向图。该算法由理查德·贝尔曼（Richard Bellman）和莱斯特·福特（Lester Ford）共同提出，能够检测图中是否存在负权回路，并计算从源点到所有其他顶点的最短路径。

== 算法原理 ==
Bellman-Ford算法的核心思想是通过'''松弛操作'''（Relaxation）逐步逼近最短路径。算法重复对所有边进行松弛，共进行<math>|V|-1</math>次（<math>|V|</math>为顶点数），确保最短路径的正确性。如果在第<math>|V|</math>次松弛后仍能更新距离，则说明图中存在负权回路。

=== 松弛操作 ===
对于边<math>(u, v)</math>，松弛操作定义为：
<math>
\text{if } d[v] > d[u] + w(u, v) \text{, then } d[v] = d[u] + w(u, v)
</math>
其中<math>d[v]</math>表示当前源点到顶点<math>v</math>的最短距离估计值，<math>w(u, v)</math>为边<math>(u, v)</math>的权重。

=== 伪代码 ===
<syntaxhighlight lang="python">
function BellmanFord(graph, source):
    distance = array of size |V| initialized with infinity
    distance[source] = 0

    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in graph:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w

    for each edge (u, v) with weight w in graph:
        if distance[u] + w < distance[v]:
            error "图中存在负权回路"

    return distance
</syntaxhighlight>

== 示例与解释 ==
=== 输入图示例 ===
考虑以下有向图（边权可能为负）：
<mermaid>
graph LR
    A((A)) -->|4| B((B))
    A -->|5| C((C))
    B -->|-1| D((D))
    C -->|2| B
    C -->|3| D
</mermaid>

=== 执行步骤 ===
以顶点<code>A</code>为源点，执行Bellman-Ford算法：
1. 初始化：<code>distance = [0, ∞, ∞, ∞]</code>
2. 第1轮松弛：
   - 更新<code>B</code>为4，<code>C</code>为5
   - 通过<code>B</code>更新<code>D</code>为3
   - 通过<code>C</code>更新<code>B</code>为7（不更新，因为4 < 7）
   - 通过<code>C</code>更新<code>D</code>为8（不更新，因为3 < 8）
3. 最终结果：<code>distance = [0, 4, 5, 3]</code>

=== 代码实现 ===
<syntaxhighlight lang="python">
def bellman_ford(graph, source):
    V = len(graph)
    distance = [float('inf')] * V
    distance[source] = 0

    for _ in range(V - 1):
        for u in range(V):
            for v, w in graph[u]:
                if distance[u] + w < distance[v]:
                    distance[v] = distance[u] + w

    # 检测负权回路
    for u in range(V):
        for v, w in graph[u]:
            if distance[u] + w < distance[v]:
                raise ValueError("图中存在负权回路")

    return distance

# 示例图的邻接表表示
graph = [
    [(1, 4), (2, 5)],  # A
    [(3, -1)],          # B
    [(1, 2), (3, 3)],   # C
    []                  # D
]
print(bellman_ford(graph, 0))  # 输出: [0, 4, 5, 3]
</syntaxhighlight>

== 时间复杂度分析 ==
* 时间复杂度：<math>O(|V| \cdot |E|)</math>，其中<math>|V|</math>为顶点数，<math>|E|</math>为边数。
* 空间复杂度：<math>O(|V|)</math>（存储距离数组）。

== 实际应用场景 ==
1. '''网络路由协议'''：如RIP（Routing Information Protocol）使用类似Bellman-Ford的算法计算最优路径。
2. '''金融套利检测'''：将货币兑换视为图，通过检测负权回路发现套利机会。
3. '''交通路径规划'''：处理包含拥堵费用（可能为负）的路线优化。

== 与Dijkstra算法的对比 ==
{| class="wikitable"
|+
! 特性
! Bellman-Ford
! Dijkstra
|-
| 负权边
| 支持
| 不支持
|-
| 负权回路检测
| 能检测
| 不能检测
|-
| 时间复杂度
| <math>O(|V| \cdot |E|)</math>
| <math>O(|E| + |V| \log |V|)</math>
|}

== 练习问题 ==
1. 修改上述代码，使其输出最短路径而非仅距离。
2. 构造一个包含负权回路的图，验证算法的检测功能。
3. 分析Bellman-Ford算法在稀疏图和稠密图中的性能差异。

== 总结 ==
Bellman-Ford算法是解决单源最短路径问题的通用工具，尤其适合含负权边的场景。尽管时间复杂度较高，但其负权回路检测能力和实现简单性使其在特定领域不可替代。理解其松弛操作的动态逼近过程是掌握该算法的关键。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]