负环与差分约束

1. 负环

负环是指一个环的边权值之和为负数。有负环的图没有最短路。

要判断一个图是否有负环，一般使用 Bellman-Ford 算法或 SPFA 算法。

Bellman-Ford

如果一个图没有负环的话，最短路径最多会经过 \(N-1\) 条边。

如果有，那么在进行 \(N\) 次更新后还能继续更新。

于是用 Bellman-Ford 求解最短路。在更新 \(N\) 次后，如果还能继续更新，那么就说明有负环。

例题 洛谷-P3385

本题可以用 Bellman-Ford 来判断负环。但是题目要求的是判断从顶点 \(1\) 出发能到达的环，而 Bellman-Ford 用来判断整个图中的环，因此不能直接使用。

SPFA

最短路最多经过 \(N-1\) 条边。如果一个点的最短路边数大于等于 \(N\)，就说明有负环。用 \(tot_i\) 表示初始点到 \(i\) 的最短路所经过的边数，每次在成功更新距离后更新所经过的边数。代码如下。

if(ds[u]+w<ds[v]){
  ds[v]=ds[u]+w;
  tot[v]=tot[u]+1;
  if(tot[v]>=n){
    return 1;
  }
  if(!vs[v]){
    vs[v]=1;
    q.push(v);
  }
}

接下来将用 SPFA 实现 洛谷-P3385。

代码