Bellman-Ford 算法检测负权环

题目描述
给定一个带权有向图，其中边权可以是负数。要求判断图中是否存在从源点 s 可达的负权环（即环上所有边的权重之和为负数）。如果存在，则输出一条包含负权环的路径；否则报告不存在负权环。

解题过程

1. 问题分析

   • 负权环是指一个环，其边权总和为负。如果存在从源点 s 可达的负权环，则 s 到某些顶点的最短路径可能无限小（通过反复绕环下降）。
   • Bellman-Ford 算法在求解单源最短路径时，可以通过第 |V| 次松弛操作是否仍能更新距离来检测负权环。

2. 算法步骤

   • 初始化：设源点 s 的距离 dist[s] = 0，其他顶点距离初始化为无穷大（∞）。
   • 松弛操作：对图中所有边进行 |V| - 1 轮松弛。每轮遍历所有边 (u, v)，检查是否可以通过 u 更新 v 的距离：
     如果 dist[u] + w(u, v) < dist[v]，则更新 dist[v] = dist[u] + w(u, v)，并记录前驱节点 prev[v] = u。
   • 检测负权环：再进行一轮松弛操作。如果任何边 (u, v) 满足 dist[u] + w(u, v) < dist[v]，则说明存在从 s 可达的负权环。
   • 还原负权环路径：通过前驱指针回溯，找到环上的一个顶点，并沿前驱链追踪直到再次遇到该顶点，从而提取整个环。

3. 详细讲解

   • 松弛的物理意义：每轮松弛尝试利用当前已知的最短路径信息，通过一条边扩展更短的路径。|V|-1 轮足以保证所有最短路径被找到（若无负权环）。
   • 负权环检测原理：若第 |V| 轮仍有距离被更新，说明存在一条路径可以通过绕环不断减小距离。
   • 路径还原技巧：
     1. 当检测到边 (u, v) 可更新时，从 v 开始沿前驱链回溯 |V| 次，确保进入环内。
     2. 再固定一个指针缓慢回溯，另一个指针快速回溯（类似Floyd判圈法），直到两指针相遇，定位环的起点。

4. 实例演示
   考虑图：顶点集 {0,1,2,3}，边 (0,1)=1, (1,2)=-1, (2,3)=-1, (3,1)=-1。

   • 初始化：dist[0]=0, 其他为 ∞。
   • 三轮松弛后，dist[1]=0, dist[2]=-1, dist[3]=-2（具体过程略）。
   • 第四轮检查边 (3,1)：dist[3]+(-1) = -3 < dist[1]=0 → 存在负权环。
   • 从前驱链 1→2→3→1 还原出环 1-2-3-1。

5. 复杂度分析

   • 时间复杂度：O(|V|·|E|)，其中 |V| 为顶点数，|E| 为边数。
   • 空间复杂度：O(|V|) 存储距离和前驱数组。

6. 常见误区

   • 注意负权环必须从源点 s 可达。若图中存在不可达的负权环，算法不会误报（因为不可达顶点的距离始终为 ∞）。
   • 若需检测整个图的负权环（无论是否可达），可添加一个超级源点，连接所有顶点（边权为0），再执行算法。

总结
Bellman-Ford 算法通过 |V| 轮松弛操作，既能求最短路径，又能高效检测负权环。关键在于理解松弛的收敛性和负权环导致无限更新的本质。