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

题目描述
给定一个带权有向图，图中可能包含负权边，但不存在负权回路（即回路的总权重为负）。请计算从某个指定的源点出发，到达图中所有其他顶点的最短路径长度。如果图中存在负权回路，算法应能检测到并报告。

解题过程

1. 问题分析
在带权图中，最短路径问题要求找到从源点到其他顶点的路径，使得路径上的边权重之和最小。当图中存在负权边时，Dijkstra算法可能失效，因为它基于贪心策略，假设一旦确定最短路径就不会被更新，但负权边可能导致已确定的路径被进一步缩短。Bellman-Ford算法通过动态规划思想，允许边的多次松弛操作，从而处理负权边的情况。

2. 算法核心思想
Bellman-Ford算法的核心是“松弛”（Relaxation）操作。对于每条边(u, v)，检查是否存在通过u到达v的更短路径：
若 dist[v] > dist[u] + weight(u, v)，则更新 dist[v] = dist[u] + weight(u, v)。
算法通过多次迭代所有边，确保最短路径被逐步传播到整个图中。

3. 算法步骤

• 步骤1：初始化
  创建一个数组dist[]，表示源点到各顶点的当前最短距离估计值。
  将源点的dist[s]设为0，其他顶点的dist[]设为无穷大（表示尚未到达）。

• 步骤2：松弛迭代
  对图中的所有边进行V-1次迭代（V为顶点数）。
  在每次迭代中，遍历每条边(u, v)，执行松弛操作：

  如果 dist[u] + weight(u, v) < dist[v]：
      更新 dist[v] = dist[u] + weight(u, v)
  

  原理：从源点到任何顶点的最短路径最多包含V-1条边，因此通过V-1次全局松弛可保证找到最短路径。

• 步骤3：检测负权回路
  再进行一次所有边的遍历：
  如果存在边(u, v)满足 dist[u] + weight(u, v) < dist[v]，说明图中存在负权回路（因为理论上V-1次迭代后不应再有更短路径）。
  若检测到负权回路，算法终止并报告错误；否则，dist[]数组即为最终的最短路径结果。

4. 举例说明
考虑以下有向图（顶点数为5，边数为8，源点为0）：
边集：
(0,1, -1), (0,2, 4),
(1,2, 3), (1,3, 2), (1,4, 2),
(3,2, 5), (3,1, 1),
(4,3, -3)

执行过程：

• 初始化：dist = [0, ∞, ∞, ∞, ∞]
• 第1次迭代：
  • 边(0,1): dist[1] = min(∞, 0-1) = -1
  • 边(0,2): dist[2] = min(∞, 0+4) = 4
  • 边(1,2): dist[2] = min(4, -1+3) = 2
  • 边(1,3): dist[3] = min(∞, -1+2) = 1
  • 边(1,4): dist[4] = min(∞, -1+2) = 1
  • 其他边无更新 → dist = [0, -1, 2, 1, 1]
• 第2次迭代：
  • 边(4,3): dist[3] = min(1, 1-3) = -2
  • 边(3,1): dist[1] = min(-1, -2+1) = -1（无变化）
  • 其他边无更新 → dist = [0, -1, 2, -2, 1]
• 第3次迭代：
  • 边(3,2): dist[2] = min(2, -2+5) = 2（无变化）
  • 无其他更新 → 结果已收敛。
• 第4次迭代（检测）：无更新，故无负权回路。
  最终最短路径：顶点0到[1,2,3,4]的距离为[-1, 2, -2, 1]。

5. 关键点总结

• 时间复杂度：O(V·E)，适用于稀疏图（E较小）或需处理负权边的场景。
• 空间复杂度：O(V)（存储dist[]数组）。
• 与Dijkstra算法的区别：Bellman-Ford能处理负权边，但效率较低；Dijkstra在无负权边时更高效（O(E log V)）。