第44课 - Bellman-Ford 算法

所属模块：图算法 难度：高级 标签：bellman-ford, negative-weight, relax

1. 学习目标

理解为什么在含有负权边的图中，Dijkstra 算法会失效，以及 Bellman-Ford 算法的必要性。
掌握 Bellman-Ford 算法的核心思想：通过反复的“松弛”操作来逼近最短路径。
实现 Bellman-Ford 算法，并能够检测图中是否存在负权环（Negative-Weight Cycle）。
分析算法的时间复杂度与空间复杂度，并了解其与 Dijkstra 算法的适用场景对比。
应用算法解决带有负权边或需要检测负权环的图论问题。

2. 核心概念

在上一课我们学习了 Dijkstra 算法，它高效地解决了单源最短路径问题。但它有一个关键的前提假设：图中所有边的权值都必须是非负的。一旦图中出现负权边（例如表示“债务”或“收益”的边），Dijkstra 的贪心策略就可能出错，因为它会“短视”地选择当前距离最小的点，却忽略了未来可能通过一条负权边获得更短路径的情况。

Bellman-Ford 算法 正是为了解决这个问题而诞生的。它由 Richard Bellman 和 Lester Ford 分别提出，能够处理包含负权边的图，并且还能检测图中是否存在从源点可达的负权环。负权环是指环路的总权值和为负数，一旦存在，从源点到该环上任意一点的最短路径就可以无限地通过绕环来减小，导致“最短路径”没有意义。

核心思想：松弛（Relaxation）

算法的核心操作称为“松弛”。想象一下，我们手里有一张图的“距离表”，记录着从源点到每个节点的当前已知最短距离估计。松弛操作就是尝试利用一条边 (u, v) 来优化节点 v 的距离。如果：dist[u] + weight(u, v) < dist[v] 那么：dist[v] = dist[u] + weight(u, v) （更新 v 的距离）同时，记录下 v 的前驱节点是 u（用于后续重建路径）。

算法流程

初始化：将源点的距离设为0，其他所有点的距离设为无穷大。
迭代松弛：重复进行 |V| - 1 次（|V|为顶点数）以下操作：遍历图中的所有边，对每条边执行一次松弛操作。因为一条最短路径最多包含 |V| - 1 条边，经过 |V| - 1 轮迭代，所有最短路径都应被“松弛”到位。
检测负权环：在第 |V| - 1 次迭代后，如果再进行一次对所有边的松弛，仍然有某个节点的距离可以被更新，那么图中必然存在从源点可达的负权环。
输出：如果没有负权环，此时 dist 数组中的值即为从源点到各点的最短路径距离。

这个“迭代所有边”的过程，使得算法能够“回顾”和“纠正”之前的错误估计，从而适应负权边的情况。

3. 代码示例

下面是一个完整的 Python 实现，包含了路径重建和负权环检测。

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数
        self.graph = []    # 存储所有边，格式为 [起点, 终点, 权值]

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        # 步骤1: 初始化距离数组和前驱数组
        dist = [float("inf")] * self.V
        dist[src] = 0
        predecessor = [-1] * self.V  # 用于重建路径

        # 步骤2: 进行 |V|-1 次松弛操作
        for i in range(self.V - 1):
            # 遍历所有边
            for u, v, w in self.graph:
                # 如果 u 的距离不是无穷大，并且通过 u 到 v 更短，则更新
                if dist[u] != float("inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    predecessor[v] = u

        # 步骤3: 检测负权环
        # 再进行一次遍历，如果还能松弛，则存在负权环
        for u, v, w in self.graph:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                print("图中存在从源点可达的负权环！")
                return None, None  # 无解

        # 步骤4: 输出结果（无负权环的情况）
        self.print_solution(dist, src, predecessor)
        return dist, predecessor

    def print_solution(self, dist, src, predecessor):
        print(f"从顶点 {src} 出发的最短距离:")
        for i in range(self.V):
            if dist[i] == float("inf"):
                path = "不可达"
            else:
                # 简单重建路径（这里只输出距离，完整路径重建可自行实现）
                path = str(dist[i])
            print(f"顶点 {i}: 距离 = {path}")

# 测试1: 含有负权边但无负权环的图
g1 = Graph(5)
g1.add_edge(0, 1, -1)
g1.add_edge(0, 2, 4)
g1.add_edge(1, 2, 3)
g1.add_edge(1, 3, 2)
g1.add_edge(1, 4, 2)
g1.add_edge(3, 2, 5)
g1.add_edge(3, 1, 1)
g1.add_edge(4, 3, -3)

print("=== 测试1: 无负权环 ===")
g1.bellman_ford(0)

# 测试2: 含有负权环的图
g2 = Graph(3)
g2.add_edge(0, 1, 1)
g2.add_edge(1, 2, -3)
g2.add_edge(2, 0, 1)  # 环 0->1->2->0 的权值和为 1 + (-3) + 1 = -1，是一个负权环

print("\n=== 测试2: 有负权环 ===")
g2.bellman_ford(0)

运行结果预期：

测试1：会正确输出从顶点0到其他顶点的最短距离。
测试2：会打印“图中存在从源点可达的负权环！”的警告，并返回None。

4. 实践练习

练习1（基础）： 运行上面的代码，分析测试1的输出。手动计算图中从顶点0到顶点3和顶点4的最短路径，验证程序结果。

练习2（中等）： 修改 Graph 类，增加一个 print_path(src, dest) 方法，利用 predecessor 数组，能够打印出从 src 到 dest 的具体路径（例如 0 -> 1 -> 4）。

练习3（进阶）： 思考并简要回答：为什么 Dijkstra 算法在存在负权边的图中会给出错误结果？请用一个包含3个节点的简单例子（如 A->B: 1, A->C: 5, C->B: -3）来说明。

5. 常见错误

迭代次数错误：误以为只需要遍历 |V| 或更少次。最短路径最多包含 |V|-1 条边，因此必须进行 |V|-1 轮松弛，再加一轮检测负权环。
遗漏负权环检测：实现时只进行 |V|-1 次迭代就输出结果，忽略了第 |V| 次迭代的检查。这可能导致在存在负权环时，程序给出一个“看似正确”但实际上无意义的结果。
邻接矩阵实现时的陷阱：如果用邻接矩阵存储图，初始化时需要将非无穷大的距离dist[v]设置为一个很大的数（如float('inf')），但松弛判断条件中，需要加上 dist[u] != float('inf')，避免从不可达的节点出发进行无效更新。
忘记处理“不可达”节点：在最终输出时，仍为float('inf')的节点代表从源点不可达，需要特殊处理，不要直接输出inf。

6. 小结

Bellman-Ford 的核心价值在于能够处理负权边和检测负权环，这是 Dijkstra 算法无法做到的。
算法精髓是通过 |V|-1 轮对所有边的松弛操作，逐步逼近真实最短路径。
负权环检测是第 |V| 轮松弛，若仍有更新则说明存在从源点可达的负权环，此时最短路径问题无解。
时间复杂度为 O(VE)，其中 V 是顶点数，E 是边数。这比 Dijkstra 算法（使用优先队列时为 O((V+E)logV)）要慢，因此在没有负权边的情况下，通常优先使用 Dijkstra。
应用场景：网络路由（如 RIP 协议）、金融套利检测、任何可能涉及“增益”或“损失”的路径优化问题。

练习编辑器

rust