一个重要的定理(Negative Cycle Optimality Conditions)：一个流的费用是最小的(在大小相同的流之中)，当且仅当它对应的残量网络中不存在负环。

正方向是显然的，反方向不好证明，本文暂时略过。

由这个定理，我们可以得到负环消去算法：先找到一个最大流，然后不停地找负环，沿负环增广，直到没有负环为止。

但是更常见的算法是 SSP (Successive Shortest Path) 算法，也就是把EK算法中的bfs换成SPFA。要证明这个算法的正确性，我们需要证明算法过程中不会产生负环。

欲证明：如果一个残量图中没有负环，那么经过一条最短路增广之后不会产生负环

证明：

使用反证法。

假设沿最短路$S$增广后产生了一个负环$C$，由于原先没有负环，$S$必定与$C$的反向路径$C'$有一个非空交集$A'$。因为$C$是负环，所以$cost(A)+cost(C-A)=cost(C)<0$，于是$cost(C-A)<-cost(A)=cost(A')$，因为$C-A$增广前后没有变化，所以$C-A$在增广之前的图中存在，把$S$中$A'$替换为$C-A$，会得到一条新的路径$S'$，也可能还会出现与$S'$不相连的几个环圈，但是注意到这几个环圈肯定在增广之前就存在(因为$C-A$增广前后没有变化)，而且增广前没有负环，所以$S'$一定比$S$更短，但是这与$S$是最短路矛盾。

Q.E.D