Bellman-Ford算法检测负权环

题目描述
给定一个带权有向图，其中边的权重可以是正数、负数或零。要求设计一个算法，不仅能计算从单个源点到所有其他顶点的最短路径，还能检测图中是否存在从源点可达的负权环（即总权重为负的环路）。如果存在这样的环，算法应正确报告；否则，输出最短路径长度。

核心思路
Bellman-Ford算法通过松弛操作（Relaxation）逐步逼近最短路径。若图中不存在负权环，最多经过\(V-1\)轮松弛可得到最短路径；若第\(V\)轮松弛仍能更新路径，说明存在负权环。

解题步骤

1. 初始化

   • 设图有\(V\)个顶点、\(E\)条边，源点为\(s\)。
   • 创建距离数组dist[]，初始化dist[s] = 0，其他顶点距离为无穷大（如INF）。

2. 松弛操作

   • 对每条边\((u, v)\)，检查是否可通过\(u\)缩短\(v\)的距离：

\[ \text{if } dist[u] + w(u, v) < dist[v] \text{, 则 } dist[v] = dist[u] + w(u, v) \]

• 重复此操作\(V-1\)轮，确保最短路径收敛（因为最短路径最多包含\(V-1\)条边）。

3. 检测负权环

   • 执行第\(V\)轮松弛：若任何顶点的距离仍可被更新，说明存在从源点可达的负权环。
   • 原理：若无负权环，\(V-1\)轮后应已收敛；额外更新表明存在无限降低路径权重的环。

4. 示例分析

   • 假设图包含边：
     \(A \to B (w=1)\), \(B \to C (w=-1)\), \(C \to A (w=-1)\)，源点为\(A\)。
   • 第1轮后：dist[B]=1, dist[C]=0（通过A→B→C）。
   • 第2轮后：dist[A]=-1（通过C→A），其他点更新。
   • 第3轮（第\(V\)轮）：dist[B]=0（通过A→B）被再次更新，确认存在负权环。

关键点

• 时间复杂度：\(O(VE)\)，适用于稀疏图。
• 负权环检测需额外一轮松弛，若报告存在环，则实际环可通过反向追踪前驱节点确定。
• 若源点不可达负权环，算法仍能正确计算源点到其他点的最短路径。