负环

如果图中存在负环，则无论经过多少次迭代，总存在有向边 $(x,y,z)$ 使不等式 $dis[y]>dis[x]+z$ 成立，即 $dis[y]-dis[x]>z$ 成立。根据抽屉原理，由起点出发的最短路经过的边数一定是小于 $n$ 的。

Belman-Ford 判定负环

若 $n$ 轮迭代之后，算法仍未结束，则图中存在负环。

若 $n-1$ 轮迭代内，算法结束，则图中不存在负环。

SPFA 判定负环

设 $cnt[x]$ 表示从起点 $1$ 到节点 $x$ 的最短路径所经过的边数。初始 $cnt[1]=0$，当满足 $dis[y]>dis[x]+z$ 时，$cnt[y]=cnt[x]+1$。此时若 $cnt[y]\ge n$，则说明存在负环，算法结束。

一般情况下，我们使用 SPFA 判定负环，因为其时间复杂度较低。

/*
    与其从每个节点出发尝试寻找负环，不如在原图的基础上建立虚拟源点
    原图存在负环，则从虚拟源点出发一定可以找到该负环

    虚拟源点与原图中每个节点相连，边权为 0，则 dis[i] = 0
*/
bool spfa() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
        vis[i] = true;
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = false;

        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (dis[y] > dis[x] + w[i]) {
                dis[y] = dis[x] + w[i];
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n) return true;
                if (!vis[y]) {
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }

    return false;
}

差分约束

差分约束系统定义为一种特殊的 $n$ 元一次不等式组，它由 $n$ 个变量 $x_1,x_2,\cdots ,x_n$ 和 $m$ 个约束条件组成，形式如下：$x_i-x_j\le c_k$， 其中 $1\le i,j\le n,i\ne j,1\le k\le m$, $c_k$ 是常数。问题是判断是否存在一组实数解 $x_1,x_2,\cdots ,x_n$，使得所有约束条件同时成立，否则判断无解。

差分约束系统可以转化为图论中的最短路问题，即对于每个约束条件 $x_i-x_j\le c_k$ （可以转化为 $x_i\le x_j+c_k$， 即图论中的 $dis[y]\le dis[x]+z$），在图中添加一条从 $j$ 到 $i$ 的边，边权为 $c_k$。此时，若存在负环，则说明无解；若存在最短路，则说明有解，且最短路长度即为 $x_i$ 的值。

常用变形技巧：

条件	转化	建边
$x_i-x_j\le c_k$	$x_i\le x_j+c_k$	$add(j,i,c_k)$
$x_i-x_j\ge c_k$	$x_i\ge x_j+c_k$	$add(i,j,-c_k)$
$x_i=x_j$	$x_i-x_j\le 0$ 且 $x_j-x_i\le 0$	$add(j,i,0)$ 且 $add(i,j,0)$