网络流算法详解

网络流算法详解网络流算法在许多实际问题中有应用，如匹配问题，著名的Hall婚姻定理。这里不证明“最大流最小割定理”，简单解释求最大流的Ford-Fulkerson算法。接下来分别详述时间复杂度为O(VE2)的Edmonds-Karp算法和时间复杂度为O(V2E)的Dinic算法。至于较新的预留推进算法就不介绍了，这个算法证明比较难，感兴趣的可以看看算法导论。本文所用到的网络流如图1，s为原点，t为汇点，边上的值表示边的容量c(u,v)，如c(s,v1)=15，c(v1,v2)=8。流用符号f(u,v)表示，如图2，流的容量f(s,v1)=10，f(v1,v2)=5。剩余容量cf(u,v)=c(u,v)-f(u,v)。在原剩余网络中找到一条流后，修改原网络边的剩余容量得到剩余网络Gf，如图3所示。注意剩余网络中有一些新添加的边即反向边的容量，为流的反馈。在图3中，有f(v1,v3)=5,那么有f(v3,v1)=-f(v1,v3)=-5，然后cf(v3,v1)=c(v3,v1)-f(v3,v1)=0-(-5)=5。sv1v2v4v3t15124916582637图1网络流的一个例子sv1v2v4v3t10/155/124/40/99/165/55/80/25/60/34/7图2图1的一条流fsv1v2v4v3t574137532183图3有图2产生的剩余网络Gf105951.Ford-Fulkerson算法算法的主要思想：1）初始化一条容量为0的流f和一个剩余网络Gf，第一个剩余网络为原图G，每条边的剩余容量初始化为每条边的初始容量cf(u,v)=c(u,v)。2）在剩余网络Gf中寻找增广路径p，取增广路径p中的边的剩余容量cf(u,v)最小值作为流的增量△f，使得f’=f+△f。修改剩余图中每条边的容量cf’(u,v)=cf(u,v)-△f得到剩余网络Gf。（补充说明：原算法中的△f可以为单位1）3）重复步骤2），直到找不到一条增广路径为止。寻找一条增广路径的方法如图4所示，然后确定增广路径上的流增量△f。本例中△f=3。图4在图3的剩余图中寻找一条增广路径P图5确定图4中增广路径P的流增量△f7sv1v2v4v3t5413753218310595sv1v2v4v3t3/50/40/133/70/53/30/20/10/83/30/100/50/90/70/5整个网络可以用邻接表或矩阵表示，网络的边即为矩阵中的元素，网络的节点则为矩阵一维的下标。这里网络中每条边最好用一个结构体表示。结构体包含边的容量和每次通过的流量这两个变量。下面是一个例子：sv1v2v4v3t15124916582637(a)sv1v2v4v3t12/1512/120/40/912/160/50/80/20/60/30/7sv1v2v4v3t312494582637(b)sv1v2v4v3t15/1512/120/40/912/163/53/80/23/60/30/71212sv1v2v4v3t12494252367(c)sv1v2v4v3t15/1512/124/40/916/163/53/80/23/60/34/7151233sv1v2v4v3t12413252363(d)153316Ford-Fulkerson算法的伪代码如下：Ford-Fulkerson(G,s,t)1foreachedge(u,v)E[G]//初始化每条边的流量为02{f[u,v]03f[v,u]04}5//GfG//初始化剩余网络Gf为原网络G，这里不需要代码6whilethereexistsapathpfromstotinthenetworkGf//网络中还存在增广路径，仍然进行迭代7{searchapathpfromnetworkGf//Karp算法采用广度优先，Dinic算法采用深度优先8cf(p)Min{cf(u,v)|(u,v)isinp}//确定增广路径上的流增量△f(p)=cf(p)9foreachedge(u,v)inp10{f[u,v]f[u,v]+cf(p)//增加剩余网络中增广路径上每条边的流量11f[v,u]-f[u,v]//显然该路径上反方向上的容量为负12cf[u,v]c[u,v]–f[u,v]//计算剩余网络Gf中的每条边的容量13cf[v,u]c[v,u]–f[v,u]14}15}2.Edmonds-Karp算法Edmonds-Karp算法与Ford-Fulkerson算法的区别在于在Ford-Fulkerson算法的第7行，Edmonds-Karp算法采用广度优先算法（BFS）寻找一条从s到t最短增广路径p代替Ford-Fulkerson的随机寻找一条从s到t增广路径p。引理1：在网络G=V,E中，原点为s，汇点为t。Edmonds-Karp算法中，对于任意顶点vV–{s,t}，在剩余网络Gf中的距离f(s,v)和f(v,t)随着流的增加而单调递增。（每次增加两个单位，这里要用到BFS生成最短路径的性质，由于这次的增广路径在剩余网络中已经是最短路径了，在新的剩余网络中，通过(s,v)的最短路径要增加。证明略）引理2：流增加的总次数不超过O(VE)。证明（1）：若在剩余图Gf中的边(u,v)满足c(u,v)=cf(u,v)，边(u,v)是一条关键边。每次进行增广路径扩充后，关键边(u,v)不会在该次的剩余网络Gf中出现。每次扩充至少会有一条关键边。可以证明网络中的每条边称为关键边至多|V|/2-1次。所以流增加的总次数为O(VE)。证明（2）：当边(u,v)在上一次剩余网络Gf中第一次称为关键边时，有f(s,v)=f(s,u)+1成立。然后边(u,v)将不会在该次剩余网络Gf’中，边(u,v)下一次出现在某个剩余网络中的时候有，肯定有流通过边(v,u)。假设当这种情况发生时，有网络Gf’’的流为f’，我们有：其中由引理1：f‘(s,v)f(s,v)，有f’(s,u)=f‘(s,v)+1f(s,v)+1=f(s,u)+2所以从s到u的路径中，当其中的一条边称两次为关键边的时候，s到u的距离增加2个单位。s到v的距离最长为n-1，那么s到u的最长距离为n-2。所以边(u,v)能成为关键边的次数最多为n/2-1次。所以流增加的总次数为O(VE)。Edmonds-Karp算法的时间复杂度：O(VE2)由引理2可知，流增加的总次数不超过O(VE)，又每次扩充增广路径的时间复杂度为O(E)，故Edmonds-Karp算法的时间复杂度为O(VE2)。3.Dinic算法Dinic算法要用到层次图的数据结构，即MSN(Multi-StageNetwork)。MSN可由每次计算得到的剩余网络Gf再计算得到。定义1：k-阶图，k-stage图(或网络)G=(V,E)是一个有向图，G的顶点集合被分成(k+1)2个不相交的集合Vi，0ik。如果有边(u,v)∈E，则有uVi和vVi+1，对某个i∈[0,k-1]成立。V0=s，Vk=t。k-阶图和k-阶图中的一条阻塞流如下图所示。图中6产生了一条阻塞流表示在该图上从原点s到汇点t再不可能增加新的流了。定义2：饱和边，如果边(u,v)满足f(u,v)=c(u,v)。定义3：流f称为网络G的阻塞流，当且仅当从s到t的任何一条路径中都包含一条饱和边。usxtvy(a)一个3-阶图usxt1/10/110/11/1vy0/11/10/1(b)一条阻塞流的例子图6k-阶图Dinic算法中用到的MSN数据结构(多阶网络)如下图8所示。MSN可以在剩余网络Gf中用BFS算法构建，时间复杂度为O(|V|+|E|)。要得到Dinic算法使用的MSN还需要一些简答的处理，如图7中，利用BFS得到的MSN可能含有边不能到汇点t，所以在计算MSN的过程中需要将这种边除去。如图8中的边(v3,x)。图7一个剩余网络Gf图8剩余网络图7Gf的一个MSN引理1：Dinic算法中每次迭代后，MSN的阶数至少增加2。假设流f*是一个由Gf计算得到的MSNf的阻塞流，f’=f+f*，令MSNf’和MSNf为Gf’和Gf计算得到的MSN。f’(s,t)和f(s,t)分别是在MSNf’和MSNf上从s到t的最短路径。我们仅仅需要证明f’(s,t)=f(s,t)+2，除非t不在MSN中。考虑任何一条从s到t的路径p，明显有|p|=f’(s,t)。如果我们假定路径p上所有的边都在MSNf’上，那么流f*将不是一条阻塞流，因为我们可以继续增大在MSNf上的路径p的流f的容量，使得MSNf上的路径p的边至少有一条边成为饱和边，那么该边将不会在MSNf’上出现。所以这里必有一条边(u,v)将不会在MSNf’上出现。令边(u,v)是在MSNf上出现而不会在MSNf’上出现的边。当边(u,v)再次出现的情况是因为边(v,u)成为增广路径p’上的一条饱和边。这意味着有f(s,v)=f(s,u)+1；f’(s,u)=f’(s,v)+1。因为边(u,v)在路径p上，由第2节中的引理1可知，f(s,u)f’(s,u)和f(s,v)f’(s,v)成立。所以我们得到f(s,t)=f(s,v)+f(v,t)=f(s,u)+1+f(v,t)=(f(s,v)-1)+1+(f(u,t)-1)=f(s,v)+1+f(u,t)-2f’(s,v)+1+f’(u,t)-2=f’(s,v)+f’(u,t)-1=f’(s,v)+(f’(v,t)-1)-1sv1v2v3v4131416412t20x8sv1v2v3v410413141647129t20x108=f’(s,t)-2引理2：Dinic算法迭代的轮数至多为n/2，即计算MSN的次数为O(V)。第一个MSN的计算式从流f初始化为0开始的（见后面算法伪代码），用Dinic算法又计算了MSNk次。由引理1可知，1+2k≦n-1，因为任何路径的长度，包括f(s,t)都小于或等于n-1，所以kn/2-1，引理得证。引理3：Dinic算法每次计算阻塞流的时间复杂度为O(VE)。阻塞流的寻找可以采用DFS算法。在MSN中从源点s出发寻找一条阻塞流f*，初始化f*=0。我们利用栈Stack来构建DFS算法寻找一条阻塞流，压栈到最深的一个节点后，然后当一个节点v从栈Stack中Pop出来后，分两种情况讨论：1）v=t因为存储在栈Stack中的顶点序列从栈底到栈顶为一条从s到t的路径，也是MSN中从s到t的一条最短路径p。令cf(p)为路径p的容量。在剩余网路Gf中增加路径p上的流f*的容量至cf(p)，然后计算新的MSNf’。对于在MSNf中的路径p的每条边(u,v)，减去容量cf(p)。如果该边的容量减少至0后，就将该边标记成饱和边。在MSNf’中这条边就不存在了，相反在Gf’中会有一条反向的边出现。2）v≠t这意味着顶点v不能到达汇点t，也即是栈中的路径从s只能最终到达v不能到达t，需要退栈。从新选择新的边压栈。每次DFS的时间为O(n)，因为在MSNf中路径的长度最多为n-1，每次压栈到顶点t后，开始出栈，修改边的容量，若该边为饱和边则在MSNf中去掉该边。然后，继续退栈，寻找新的边入栈新的顶点，如此反复进行DFS收索直到一条阻塞流f*产生。实际情况中阻塞流f*产生后，MSNf中已经没有从源点s到达汇点t的边了。所以在MSNf中利用DFS寻找一条阻塞流f*的时间复杂度为O(VE)。引理4：Dinic算法的时间复杂度为O(V2E)。由引理2和引理3可知Dinic算法的时间复杂度为O(V2E)。Dinic算法伪代码Dinic(G,s,t)1foreachedge(u,v)E[G]2{f[u,v]03f[v,u]04}5GfG6ComputetheMSNforGfstartingfromsources7whilesinktisinMSN8{findablockingflowf*inMSN9foreachedge(u