图论之最大流问题（三）

在前几天的文章里面，我们讲到求解最大流的关键是找到增广路，并且单独介绍了一个求增广路的Ford-Fulkerson算法，也叫做标号法。事实上还有许多别的求增广路的算法，今天我们就再介绍一个“最短增广路”算法。

最短增广路的思想其实很简单，既然需要找一条增广路来优化，那就直接找最短的那条增广路吧。

首先介绍两个重要概念，一个叫残留量：给定容量网络G(V, E)及可行流f，弧上的残留容量记为c'(u, v)= c(u, v)–f(u,v)。每条弧的残留容量表示该弧上可以增加的流量。因为，从顶点u到顶点v流量的减少，等效于顶点v到顶点u流量增加，所以每条弧上还有一个反方向的残留容量c'(v,u) =–f(u,v)。由残留量组成的网络叫做残留网络，下面给个例子：

上图a中的两个数字分别表示弧的容量和已经用掉的容量。

注意b图，它里面各个点之间其实有一个层次关系，比如Vs是第0级，V1和V2是第一级，等等。下面是网络节点按级划分的结果：

对残留网络分层后，删去比目的点Vt层次更高的顶点和与目的点Vt同层的顶点，然后删去与这些顶点关联的弧，再删去从某层顶点指向同层顶点和低层顶点的弧，所剩的各条弧的容量与残留网络中的容量相同，这样得到的网络是残留网络的子网络，称为层次网络。

解释一下构造层次网络的时候为什么要这么删除多余的边：删除比Vt层次更高，以及同级别的点的原因很简单：Vt是目的点，不允许有从Vt中流出的流量。删除指向同层以及底层的边是因为我们要找的是最短增广路，留着这些边会把增广路边长。有人可能会问，少考虑了一些潜在的增广路，不会对最终结果有影响么？别担心，当前的增广路被处理完之后，在下一轮循环里就不再考虑了，此时这些上一轮没有考虑到的、仍旧有剩余流量的边就会被考虑到的。

不知道大家注意到没有，层次网络中任何一条连接源点Vs和目的点Vt的通路都是一条增广路，并且是最短的增广路。

知道寻找最短增广路之后问题就简单了，找到之后优化它，然后重新找找看还有没，还有增广路的话继续优化，直到不存在增广路为止。

n