编辑“︁Bellman-Ford算法”︁（章节）

== 示例与解释 ==
=== 输入图示例 ===
考虑以下有向图（边权可能为负）：
<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>