3 负环及其应用
3.1 判定算法
判断负环只能用“边松弛”算法，也就是Bellman-Ford和SPFA算法。这两个算法都是(O(NM))级别的。因为负环中一定存在一条负边，使得(dis_i > dis_j+d(i,j))恒成立。因此，在用边松弛算法时，如果一条边被松弛超过一定次数，我们就可以判定图中存在负环。负环则代表环上的边权和小于0。在负环上走若干圈，则(dis_i)可以趋近(-infty)。
Bellman-Ford算法
如果经过(n)轮迭代后，仍然有边可以被更新，则图中存在负环。
否则，如果在(n-1)轮迭代后，如果不能更新任何一条边，则图中不存在负环。
SPFA算法
设(|Gamma_i|)表示从源点到(i)的最短路包含的边数。规定(|Gamma_S|=0)。当转移(dis_y = dis_x + d(x,y))成立时，我们同时令(|Gamma_y| = |Gamma_x| + 1)。在任意时刻，如果有(|Gamma_y| geq n)，则图中有负环。
我们也可以用入队次数来判断。如果一个节点被入队(n)次以上，则图中存在负环。
当然，前面也介绍过一种基于DFS的SPFA判断负环的方法。这种方法速度较快，但是比较专一。在计算最短路时，效率远不如基于队列的SPFA。
3.2 应用
其实比较灵活。只介绍一些比较简单的应用
图上二分
极少数题目会出现。由于本人做题不多，这里只能给出一道例题：HNOI2009 最小圈。
由于答案具有单调性——即不存在小于答案的平均值，而一定存在大于等于答案的平均值，我们可以二分求出最小值。设这个平均值为(ar{w})，那么根据平均值的性质，对于环上的边(w_i)，有(sum_{i=1}^{0}(w_i-ar{w})=0)。我们二分这个平均值(ar{w})，然后把每条边的边权设置为(w_i-ar{w})。如果图中存在一个负环，说明当前平均值合法，可以进一步缩小。时间复杂度可以看作(Omega(mlog W))。当然，最坏情况还是(O(nmlog W))的。其中(W)表示边权的上下界之差。
差分约束系统
是一种特殊的(N)元一次不等式组。其中每一个不等式都形如(X_i - X_j leq c_k)。通过移项，我们可以得到一个不等式：(X_i leq X_j + c_k)。这个不等式酷似我们之前所讲到的三角形不等式。我们的目标就是求出一组(X_i)使得每一个三角形不等式成立。对于(X_i - X_j geq c_k)的不等式，可以转换为(X_j - X_i leq -c_k)的形式解决。
注意到如果({X_i})是一组解，那么通过加上一个常数(c)，我们可以得到另一组解({X_i+c})。我们不妨假定每一个变量都是负数或0，设(X_0 = 0)，令(X_i leq 0)，则(X_i - X_0 leq 0)。我们由(X_0)向所有点连一条边权为0的边，然后对于所有(X_i - X_j leq c_k)的边，我们往(j)从(i)连一条边。这时，(X_i)的实际意义就是从(0)点到(i)点的最短距离。用最短路算法就可以求出一组负数解。
当构造出来的图中存在负环，(X_i)会被不断更新：说明(X_i)的值始终无法满足每个不等式。此时这个差分约束系统无解。由于既要求出最短路，又要判断负环，这里应该使用SPFA。