图的单源最短路径：Bellman-Ford算法

描述
Bellman-Ford算法是一种用于求解带权图中单源最短路径问题的算法，适用于包含负权边的图（但不能有负权环）。与Dijkstra算法不同，Bellman-Ford通过动态规划思想，对图中所有边进行多次松弛操作，逐步逼近最短路径的解。其时间复杂度为O(V·E)，其中V是顶点数，E是边数。

核心思想

1. 初始化：将源点到所有顶点的距离初始化为无穷大（∞），源点到自身的距离设为0。
2. 松弛操作：对每条边进行遍历，尝试更新源点到该边终点的最短距离。
3. 重复松弛：重复上述过程V-1次（最坏情况下需要V-1轮更新才能保证找到最短路径）。
4. 负权环检测：再进行一次松弛操作，若任何顶点的距离仍可被更新，说明图中存在负权环。

详细步骤

步骤1：初始化距离数组

• 创建一个数组dist[]，长度为V（顶点数），dist[s] = 0（s为源点），其余初始化为∞。
• 例如，对于有向图（s→A权重2，s→B权重4，A→B权重-1），初始化后dist[s]=0, dist[A]=∞, dist[B]=∞。

步骤2：进行V-1轮松弛操作

• 每一轮遍历所有边，对每条边(u, v, w)（u为起点，v为终点，w为权重）执行：

  if dist[u] + w < dist[v]:  
      dist[v] = dist[u] + w  
  

• 第1轮示例：
  • 边(s→A, 2)：dist[s]+2=0+2=2 < ∞，更新dist[A]=2。
  • 边(s→B, 4)：dist[s]+4=4 < ∞，更新dist[B]=4。
  • 边(A→B, -1)：dist[A]+(-1)=2-1=1 < 4，更新dist[B]=1。
• 后续轮次：继续遍历所有边，但若某轮中未发生任何更新，可提前终止（优化）。

步骤3：负权环检测

• 完成V-1轮后，再遍历所有边一次。若存在边(u, v, w)使得dist[u] + w < dist[v]，则说明存在从源点可达的负权环（最短路径无意义）。
• 例如，若图中存在环A→B→A，权重分别为-1和-2，则检测时会发现dist可被无限更新。

为什么需要V-1轮？

• 最短路径最多包含V-1条边（无环情况下）。每轮松弛至少确定一个顶点的最短路径，最坏情况下需V-1轮才能覆盖最长路径。

应用场景

• 含负权边的图（如金融网络中的债务关系）。
• 需检测负权环的场景（如仲裁问题）。

总结
Bellman-Ford算法以较高的时间复杂度换取对负权边的兼容性，其核心在于通过多次全局松弛操作，逐步修正最短路径估计值，最终得到可靠解或检测出负权环。