网络流问题
李晓明
在高速公路网中有车流，在互联网上有信息流，在自来水管网中有水流，在公用电网中有电流，等等。但凡网络，大都和某种流联系在一起;网络的作用，就是要保障那些流的畅通。对网络中流的研究是具有普遍意义的主题。
研究网络中的流问题可有多个不同的视角和目标追求。本文讨论两个节点之间可能经过的最大流量。我们从简单例子开始，建立讨论这个话题的语境。
图1所示为一个3节点{s，a，t}的有向网络，边上的数字表示能支持的流量（不妨看成是单位时间能通过的车辆数），一般也称为对应边的“容量”。这个例子数据表明s—a边的容量为3，a—t边的容量为2。想象为道路，也就相当于是说s—a路段要比a—t路段宽一些。边的箭头方向则表示“单行线”的方向。
现在的问题是，如果我们要不断从s发出开往t的车，单位时间能发多少辆？几乎不用多想，你马上会认识到3是不行的，最多是2。而且如果有人说1，你则会说每条边的容量都还有剩余，因而流量还可以增加。于是我们说，2就是这个网络中从s到t的最大流量。并且，如果面对的不止两个路段，而是多个如此串联的路段，你也能认识到从s到t的最大流量受限于最小容量的路段。那样的路段，也称为“瓶颈”，别的路段再宽也没有用。在本专栏前两期讨论调度问题时，我们有过一个背景不同但精神上有类似之处的概念，就是“关键路径”，它就是完成任务的瓶颈。下面考虑图2所示的一个稍微复杂一点的例子。
先看图2（a），不妨也看成是一个道路网的抽象。在讨论流问题时，总假设有一个节点是出发点，习惯上用s表示，画在图的最左端，还假设一个节点为到达点，用t表示，画在图的最右端。这个网络中还有另外两个节点a和b，以及节点之间的5条路段，它们的容量也相应标在上面。在图2（a）中，我们还看到有3条从s到t的路径：s—a—t，s—b—t和s—a—b—t。
单位时间里从s到t能发出多少辆车？显然取决于那些车走的路径。如果让它们都走s—a—b—t，如图2（b）所示，那最多是20。此时路段s—b用不上了，因为它后面的b—t已经被占满。不过，如果我们让20辆走s—a，但在a分流，10辆走a—t，10辆走a—b，同时让10辆走s—b—t，就实现了从s到t的最大流量30。图2（c）所示的，是这样一种安排的另一个视角的理解，虚线所表示的相当于是说在图2（b）已经在s—a—b—t安排了流量20的基础上，可以让从s—b来的流量（10）沿着a—b的反方向到達t。这样一种视角和前面说的在a点分流是等价的，它乍听起来不如分流的说法自然，但方便地成为我们后面讨论算法的“思想基础”。
到此，读者应该慢慢体会到这个问题的挑战之处了，如果网络稍微复杂一点，如图3（a）所示，要目测得出源s到目的t之间最大流量的安排绝非易事，因而需要算法。
首先，让我们来一般地理解一下这个问题。给定一个如图3（a）所示的网络，假设需要在每条边上做流量安排，总体体现为从s到t的流量。如果有人说他做了一个如图3（c）的安排（现在每条边上标有两个数，第一个为容量，第二个括弧中的数表示流量安排），你会有什么观感？首先，你会马上说“不靠谱”，因为在a—b边上他安排的是13，要大于网络中a—b的容量12，这是不可接受的。还有没有别的问题？还有一个也是不可接受的问题！注意节点c，进入它的流是12+0+0=12，而离开它的流是3+11=14，二者不相等，是矛盾的。也就是说，任何“可行的”安排必须满足两个条件：①每条边上流量分配不能超过边的容量;②除了出发点s和结束点t外，每个节点的“入流”必须等于“出流”。
现在你可以看看图3（b）了。有什么问题吗？它满足上述两个条件，于是我们说它是一个“可行解”，对应的总流量为11，但我们不知道它是不是“最优解”（即对应s—t之间的最大流安排）。事实上，对这个例子而言，你容易看到沿着s—a—b—t的流量并没有用尽，三条边上分别还剩16-8=8，12-6=6，20-7=13。这意味着你可以对那条路径上的流量给一个增量min（8，6，13）=6。于是得到了一个较优的可行解（此时s—a上的流量为14，a—b上的流量为12，b—t上的流量为13，总流量为17），但还是不知道是否最优。
的确，在此基础上我们进一步还看到一种增加流量的可能，类似于图2（c），此时可以在s—c上增加5，在b—c上减少5，在b—t上增加5，从而得到总流量22。也就是说，如果我们在一个可行解基础上发现一条从s到t的包含两个不同方向边的路径，在顺方向边上的容量剩余，在逆方向边上的流量均大于0，就意味着可以得到一个总流量的提升。
上述在一个可行解的基础上有两种改进思路的例子值得一般性讨论，是本文要介绍的经典Ford-Fulkerson算法（1956年发明）的关键。参考图4，假设在一个可行解基础上发现了一条如图4（a）所示的路径s—a—b—c—d—t，边上的标记x（y）表示容量为x，在当前可行解中已经分配了流量y，那么剩余可用的容量就是x-y。于是我们看到8-3=5，6-5=1，7-2=5，4-3=1和5-1=4，其中的最小值1就是还可以做的改进。边上的标记就更新为8（4），6（6），7（3），4（4）和5（2）。显然，结果依然是一个可行解。
假设发现了一个如图4（b）所示的情况呢？注意a和b之间、c和d之间边的方向是反过来的，因而现在不能说在图中发现了“一条从s到t的（有向）路径”。观察节点a，s—a边产生的入流量为3，b—a边产生的入流量为5，加起来是8。由于是可行解，在a上的入流之和要等于出流之和，因此这个8一定已被与a相关的其他出向边抵消掉了。此时，如果我们让s—a上的流量“+1”，让b—a上的流量“-1”，不会打破在节点a上的流量平衡，但破坏了节点b上的流量平衡——出流少了1。怎么办？让b—c边上的流量“+1”就可以了，但这又导致节点c上的入流多了1，解决的办法是让d—c上的流量“-1”，又造成d上的出流少了1，最后就靠在d—t上“+1”补偿，从而完成整个平衡，得到了一个总流量提高的可行解。值得指出的是，类似于图4（b）的路径上的边不一定非得是正反方向交替的。体会上述分析，我们能认识到关键是保持每个中间节点出入流量的平衡，顺向边的边“+”，逆向的边“-”。
对图4（b）这个例子而言，其实改进可以比“+1”更大。但凡需要增加流量的边，不得超过剩余容量，但凡需要减少流量的边，不得超过已分配的流量。因此我们看到8-3=5，5，7-2=5，3和5-1=4，其中的最小值3就是可以得到的最大改进。
综上所述，Ford-Fulkerson算法的基本思想就是从一个每条边流量为0的初始状态（显然是一个可行解）开始，不断发现上述两种改进的机会，直至没有新机会了。
第一种机会，就是要看能否找到一条从s到t的有向路径，其上每一条边的剩余流量都大于0。第二种机会，就是要看能否找到一条从s到t的边方向不一定一致的路径（但一定是离开s，进入t），其上顺边的剩余流量和逆边的流量都大于0。道理上就是这样的，不过后者实施起来会感觉别扭。为此，人们想出了一个好办法：将第二种情况转变为第一种，从而可以统一处理。还是以图4为例，这个办法体现在图4（c）中，我们特别注意其中增加了两条边a—b和c—d，上面标示的容量分别为b—a和d—c边上已分配的流量。这样一来，在原始图上存在一条边方向不一致的路径，就等价于在新的图上存在一条有向路径了。与第一种所有方向一致的情况一道，这样的路径统一称为“增量路径”（augmenting path）。
在程序实现中的具体做法就是，用A表示原始网络，但在算法过程中操作一个所谓剩余容量网络G。最初让G=A，一旦决定G的某条边a—b上要分配一个流量x，那么除了在a—b当前剩余容量上减x，同时也在b—a的容量上加x。这样，在当前可行解上寻找提升流量的机会，就都变成在G上寻找一条从s到t的增量路径问题。我们以前面的图2为例来看这个过程。图5（a）是图2所示网络的邻接矩阵A，也就是初始的G，其中下画线的3个数字对应找到的s—a—b—t路径，我们看到最小值为20。于是做更新，除了每一个数减去20外，在对称的地方（也就是反向边）要加20，于是得到图5（b）。
图5（b）中下画线的3个数字对应找到的是增量路径s—b—a—t，我们看到最小值为10。于是做更新，除了对应每一个数减去10外，在对称的地方要加10，于是得到图5（c）。特别注意到，a—b边上剩余流量的情况，最开始是30，然后是10，现在又变成20了。而b—a边上则是0，20，10，两条边上对应数据之和总是30，即原始网络中边上的容量。这正是两种情况交替出现可能带来的结果。
最后的流量分配在图5（d）中，它是图5（a）中的初始容量减去图5（c）中对应项的结果。
至此，可以说我们已经完成了算法的描述。宏观上即是，用给定的网络A，初始化一个称为剩余容量网络的操作网络G，不断在G上发现从s到t的有向（增量）路径，并按照所定的规则对G进行更新，直到没有s—t路径可以发现了，也就是再也没有提升可行解质量的机会了。
怎么在G上发现是否存在s—t增量路径？G是一个有向图，广度优先搜索和深度优先搜索都可以用于发现两个节点之间有向路径。在本专栏前面的文章中，我们多次用到这两种搜索方法，在此不再单独介绍。下面参照图6给出一个广度优先搜索的程序版本，看看算法的实现。
先看10～18行的主程序部分。它要控制做若干次从S开始的广度优先搜索，每次搜索若达到了目的节点t，就更新剩余流量网络G，然后继续搜索;如果没达到t，就意味着没机会了，结束。结束的时候，最大流的分配方案則由初始网络A和工作网络G中的数据直接给出（见上面讨论的图5例）。其中每次搜索的初始化，除了一般BFS都需要的队列（queue）和访问与否的标记（visited）外，还有两个特殊的针对每一个节点的标记——lead和flowcap。lead用于记录搜索过程中的上层节点，flowcap用于记录从源节点（s）经搜索路径到该节点的“饱和流量”。所谓饱和流量，指的是它与该路径上至少一条边的剩余流量相等。有了lead和flowcap，更新G就十分简单了（因而这里没有提供）。
BFS就是广度优先搜索过程，进入时queue中有源节点s。剩余流量网络G采用了矩阵表示，因而有一个for循环来看哪些节点与当前节点x相连（G[x][i]>0）且还没有被访问（not visited[i]），对那些节点做BFS所需的状态更新，并放到队列中。第8行是和这个流量问题特别相关的，得到上面提到的饱和流量。
将这个程序用在图3（a）数据上，得到的流量结果如图7（a）所示。我们能够检验前面指出的两个条件，保证它是一个可行解：①每条边上括号中的数（流量）不大于左边的数（容量）;②每个节点的入流之和等于出流之和。这时我们看到，总流量=23，要优于在前面讨论图3时提到的每一个可行解。同时，我们也指出一个网络中最大流的具体安排不一定是唯一的，图7（b）就是另外一种，这和在做路径搜索时选择节点的顺序有关。
上面比较详尽地介绍了Ford-Fulkerson算法及其程序实现。作为算法研究，还有几个问题值得考虑（下面总假设所考虑的网络是有穷的，且每条边上的容量为正整数），这里列出来并简略讨论，欢迎有进一步兴趣的读者和我们联系深入切磋。
（1）为什么这个算法一定会结束？在G上每找到一条新的路径，会对一些边的剩余容量进行更新，有的减少，有的则是增加（如图5所示网络中a—b对应的值），为什么一定会出现找不到s—t路径的情况，从而结束算法呢？可以这样考虑：源节点s出边上的容量之和是有限的（不妨记C为从s出发的剩余容量，最初就是它的出边的容量之和），算法过程中每找到一条s到t的路径（每一条边剩余容量都大于0），都会让C减少，而C有下界0（尽管不一定总达到），因此算法一定会终止。
（2）即便结束，只是说在剩余流量网络上找不到s—t路径了，为什么得到的就是最大流呢？这个问题比较难一些，通常和另外一个概念“最小割”结合起来讨论。给定一个我们关心的网络，总可以从中删除若干条边，使得不再存在从s到t的有向路径，我们称那样的边集为网络的“割”。每一个割边上的容量之和就是割的容量。具有最小容量的割就是“最小割”。容易想到，任何s—t流量都不会大于最小割的容量，于是如果一个s—t流量达到了最小割容量，那它就是一个最大流。可以证明，Ford-Fulkerson算法终止的时候得到的就是与最小割相等的流量。
（3）算法的运行时间效率如何？从图6的算法描述可以看到，要做若干次s—t路径搜索。从（1）中的讨论可知，次数不会超过s的出边容量之和C。每做一次BFS，时间与网络图中的边数（m）成正比，由于剩余容量网络G的边数每次都可能改变，但总的来说受限于节点数（n）的平方，于是可以说如此实现的是O（C*n2）算法。鉴于这个复杂性的表达与数值C相关，可能很大，人们也研究了另外的独立于C的算法。
（4）虽然我们用到了图3（a）所示网络的例子，也给出了如图7所示的结果，但在前面分析的时候没有涉及其中既有a—c边，也有c—a边的情况，在程序实现中需不需要做什么特别处理呢？仔细想想双向边的影响，能认识到在算法中不需要做特别处理，只需对结果G中的数据做恰当解释，配合初始的A，就能给出最优流量分配。
事实上，如果有双向边，也就是某些A[i，j]和A[j，i]都大于0，G的初始化也就有这样的情况。按照算法，每发现一条路径，其中边的最小剩余容量值f被用来做更新，cij←cij-f，cji←cji+f。G中的任何一条边都可能被多次发现在找到的路径上，于是上述更新对同一条边可能多次，包括反向边j—i被发现，于是会做cji←cji-f，cij←cij+f。最终，G[i，j]=cij-fij+fji，G[j，i]=cji-fji+fij，其中fij表示累积的流量更新。
如何得到A上每条边在最大流中分配的流量？看A[i，j]-G[i，j]=fij-fji和A[j，i]-G[j，i]=-（fij-fji），正好相反。哪个为正，就是在对应边上的分配，另一个则没有流量分配，即流量为0。这是因为，在两节点之间的两个反向的边上，总是可以让一条边上的流量为0。举个例子，若算法过程产生了fij=8，fji=3，从节点i和j之间经过的流量角度，等价于fij=5，fji=0。
参考文献：
[1]Jon Kleinberg.Eva Tardos， Algorithm Design（影印版）[M].北京：清华大学出版社，2006，1：338-345.
[2]陈道蓄.调度问题中的算法[J].中国信息技术教育，2020（11）：25-29.
注：作者系北京大学计算机系原系主任。
