Bellman-Ford算法求单源最短路径问题

题目描述
给定一个带权有向图，图中包含n个顶点和m条边，边权可以是负数。同时给定一个源点s，要求找出从s到图中所有其他顶点的最短路径。如果图中存在从s可达的负权环，算法应能检测并报告这一情况。

关键点分析

1. 边权允许为负数，这是与Dijkstra算法的主要区别
2. 需要处理负权环的情况（Dijkstra算法无法处理）
3. 单源最短路径：从一个起点到所有其他顶点的最短路径
4. 适用场景：有负权边但无负权环的最短路径计算

算法原理
Bellman-Ford算法基于动态规划思想，通过松弛操作逐步逼近最短路径。核心观察是：在无负权环的图中，任意两点间的最短路径最多包含n-1条边。

算法步骤详解

步骤1：初始化

• 创建距离数组dist[]，大小为n（顶点数）
• 设置dist[s] = 0，表示源点到自身的距离为0
• 设置其他所有dist[v] = ∞（无穷大），表示初始时距离未知
• 可选的前驱数组pred[]用于记录路径（非必需）

步骤2：松弛操作
松弛是算法的核心操作，定义为：对于边(u, v)权重w，如果dist[u] + w < dist[v]，则更新dist[v] = dist[u] + w

步骤3：主循环
执行n-1次循环（n为顶点数），每次循环遍历所有边：

for i = 1 to n-1:
    for each edge (u, v) with weight w in graph:
        if dist[u] ≠ ∞ and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            pred[v] = u  # 记录前驱节点

为什么需要n-1次循环？

• 最短路径最多包含n-1条边（无环情况下）
• 每次外层循环保证至少找到多一条边的最短路径
• 经过n-1次循环后，所有最短路径都应被找到

步骤4：负权环检测
再进行一次额外的边遍历：

for each edge (u, v) with weight w in graph:
    if dist[u] ≠ ∞ and dist[u] + w < dist[v]:
        return "图中存在负权环"

算法正确性证明

1. 如果没有负权环，n-1次松弛后所有最短路径都已确定
2. 如果第n次松弛还能更新距离，说明存在负权环
3. 因为负权环可以无限次绕行，使路径权值无限减小

时间复杂度分析

• 主循环：O(n)次
• 每次遍历所有边：O(m)
• 总时间复杂度：O(n×m)
• 空间复杂度：O(n)存储距离数组

实例演示
考虑有向图：顶点{0,1,2,3}，边：
0→1: 4, 0→2: 5, 1→3: 7, 2→1: -2, 2→3: 1

源点s=0，执行过程：

• 初始化：dist=[0,∞,∞,∞]
• 第1轮：更新dist[1]=4, dist[2]=5
• 第2轮：通过2→1更新dist[1]=3, 然后更新dist[3]=8
• 第3轮：无更新，算法终止

优化技巧

1. 提前终止：如果一轮中没有距离更新，可提前结束
2. 队列优化（SPFA）：只对距离发生变化的顶点的出边进行松弛

应用领域

• 网络路由协议（如RIP）
• 金融套利检测
• 图论中的负权环检测
• 作为其他算法的基础组件