网络流算法完整版本

网络流算法专题

引例：运输网络现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？4248473621STV1V2V3V4公路运输图最大流基本概念这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：有且仅有一个顶点S，它的入度为零，即d-(S)=0，这个顶点S便称为源点，或称为发点。有且仅有一个顶点T，它的出度为零，即d+(T)=0，这个顶点T便称为汇点，或称为收点。每一条弧都有非负数，叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图，记为G=(V,E,C)可行流可行流 对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。1.每一条弧(i,j)有fij≤Cij2.流量平衡 除源点S和汇点T以外的所有的点vi，恒有： ∑j(fij)=∑k(fjk)

该等式说明中间点vi的流量守恒，输入与输出量相等。3. 对于源点S和汇点T有， ∑i(fSi)=∑j(fjT)=V(f)可增广路给定一个可行流f={fij}。若fij=Cij，称<vi,vj>为饱和弧；否则称<vi,vj>为非饱和弧。若fij=0，称<vi,vj>为零流弧；否则称<vi,vj>为非零流弧。定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。譬如在图中，P=(S,V1,V2,V3,V4,T)，那么

P+={<S,V1>,<V1,V2>,<V2,V3>,<V4,T>} P-={<V4,V3>}给定一个可行流f，P是从S到T的一条道路，如果满足：

fij是非饱和流，并且<i,j>∈P+,fij是非零流，并且<i,j>∈P-

那么就称P是f的一条可增广路。之所以称作“可增广”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。剩余图(残余网络)剩余图G’=(V,E’)流量网络G=(V,E)中，对于任意一条边(a,b)，若flow(a,b)<capacity(a,b)orflow(b,a)>0则(a,b)∈E’可以沿着a--->b方向增广2007冬令营讲座剩余图中，从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中，每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小G=(V,E,C)是已知的网络流图，设U是V的一个子集，W=V\U，满足S∈U，T∈W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：割切割切示例上例中，令U={S,V1}，则W={V2,V3,V4,T}，那么，C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=17流量算法的基本理论定理1：对于已知的网络流图，设任意一可行流为f，任意一割切为(U,W)，必有：V(f)≤C(U,W)。定理2：可行流f是最大流的充分必要条件是：f中不存在可改进路。定理3：整流定理。 如果网络中所有的弧的容量是整数，则存在整数值的最大流。定理4：最大流最小割定理。 最大流等于最小割，即maxV(f)=minC(U,W)。

最大流算法第1步，令x=(xij)是任意整数可行流，可能是零流，给s一个永久标号(-,∞)。第2步(找增广路)，如果所有标号都已经被检查，转到第4步。找到一个标号但未检查的点i,并做如下检查，对每一个弧(i,j),如果xij<Cij,且j未标号,则给j一个标号(+i,δ(j)),其中，δ(j)=min{Cij-xij,δ(i)}对每一个弧(j,i),如果xji>0,且j未标号，则给j一个标号(-i,δ(j)),其中，δ(j)=min{xji,δ(i)}第3步(增广)，由点t开始，使用指示标号构造一个增广路,指示标号的正负则表示通过增加还是减少弧流量来增加还是减少弧流量来增大流量，抹去s点以外的所有标号，转第二步继续找增广轨。第4步(构造最小割)，这时现行流是最大的，若把所有标号的集合记为S，所有未标号点的集合记为T,便得到最小割(S,T)。实例复杂度分析设图中弧数为m,每找一条增广轨最多需要进行2m次弧的检查。如果所有弧的容量为整数，则最多需要v(其中v为最大流)次增广，因此总的计算量为O(mv)。proceduremaxflow;{最大流}vari,j,delta,x:integer;last:tline;{可改进路中的前趋}check:array[0..maxn]ofboolean;{检查数组}beginrepeatfillchar(last,sizeof(last),0);fillchar(check,sizeof(check),false);last[1]:=maxint;repeati:=0;repeatinc(i)until(i>n)or(last[i]<>0)andnotcheck[i];{找到一个已检查而未标号的点}ifi>nthenbreak;forj:=1tondoiflast[j]=0thenifflow[i,j]<limit[i,j]thenlast[j]:=i{正向弧}elseifflow[j,i]>0thenlast[j]:=-i;{反向弧}check[i]:=true;untillast[n]<>0;

iflast[n]=0thenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifx<deltathendelta:=x;untili=1;{求改进量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;{放大网络流}untilfalse;end;利用找增广路的其他流量算法增广路的思想在于每次从源点搜索出一条前往汇点的增广路，并改变路上的边权，直到无法再进行增广：Ford-Fulkerson算法:在剩余图中，采用深度优先每次任意找一条增广路径增广。O(k*nm)Edmonds-Karp算法:最短增广路方法(SAP),在剩余图中，用宽度优先找一条含结点数最少的增广路径增广。O(nm2)连续最短增广路方法（DINIC）：Dinic算法要用到层次图的数据结构，即MSN(Multi-StageNetwork)。MSN可由每次计算得到的剩余网络Gf再计算得到。在剩余图中，每次BFS找增广路径时，记录每个点的距离标号。即一次标号，多次增广。O(n2m)DINIC算法层次图：就是把原图中的点按照到到源的距离分“层”，只保留不同层之间的边的图。算法流程

1、根据残量网络计算层次图。

2、在层次图中使用DFS进行增广直到不存在增广路。

3、重复以上步骤直到无法增广。时间复杂度因为在Dinic的执行过程中，每次重新分层，汇点所在的层次是严格递增的，而n个点的层次图最多有n层，所以最多重新分层n次。在同一个层次图中，因为每条增广路都有一个瓶颈，而两次增广的瓶颈不可能相同，所以增广路最多m条。搜索每一条增广路时，前进和回溯都最多n次，所以这两者造成的时间复杂度是O(nm)；而沿着同一条边(i,j)不可能枚举两次，因为第一次枚举时要么这条边的容量已经用尽，要么点j到汇不存在通路从而可将其从这一层次图中删除。综上所述，Dinic算法时间复杂度的理论上界是O(n2*m)。Maxflow-DinicDinic比之朴素的最大流算法作了几点改动。①增加了一个用bfs标号的操作，对于节点i的标号dis[i]表示的是节点i到源点距离的下界（只有当前边的容量上限-已通过流量>0才可以拓展）②找增广路时再加一个限制条件：只能由标号为dis[i]的拓展到标号为dis[i]+1的。③当找不到增广路时，重新标号。当汇点没有标号时，程序结束。DINIC算法演示：源点汇点422532汇点32对增广路进行增广，增广后退回到源点1汇点232汇点1找到增广路路线，（红色路线）找到增广路路线，（红色路线）对增广路进行增广，增广后退回到源点，再无增广路线3Maxflow-Dinicvoidbh(){intstack[1001]={0},j,h,e,k;h=0;e=1;stack[1]=a[1]=1;while(h<e){h++;k=stack[h];for(j=1;j<=n;j++)if(c[k][j]-f[k][j]>0&&!hash[j)

{stack[++e]=j;hash[j]=1;dis[j]=dis[k]+1;}}}SAP:ShortestAugmentingPaths同Dinic有些类似的框架：①定义距离dis(i)为节点i到汇点距离的下界。②在初始距离标号的基础上，不断沿可行弧找增广路增广，一般采用dfs。对于可行弧(i,j)有

dis[i]=dis[j]+1;③

遍历当前节点完成后，为了使下次再来的时候有路可走（当然要满足距离标号的性质：不超过真实距离），重标号当前节点为:

dis[i]=min{dis[j]|(i,j)}+1④当源点的dis值>=总节点个数时算法结束。SAP:ShortestAugmentingPathsSAP还有一个很好很强大的优化---GAP注意到我们在某次增广后，最大流可能已经求出，因此算法做了许多无用功。可以发现，距离标号是单调增的。这启示我们如果标号中存在“间隙”，则图中不会再有可增广路，于是算法提前终止。实践中我们使用数组sum[i]记录标号为i的顶点个数，若重标号使得sum中原标号项变为0，则停止算法。

事实上这并不是SAP独有的优化，，还有一种算法HLPP也与这二者有些相似，但是使用的相对少些，这里就不介绍了.用预流推进办法求网络流预流推进算法给每一个顶点一个标号h(v)，表示该点到t的最短路（在残量网络中）。第一步hights()过程，就是BFS出初始最短路，计算出每一个顶点的h(v)。预流推进算法的特征是运用了预流来加快运算。预流说明图中的节点(除s,t)，仅需要满足流入量>=流出量。其中流入量>流出量的结点，我们称之为活动节点。我们的算法就是不断地将活动结点，变为非活动结点，使得预流成为可行流。HLPP（HighestLabelPreflowPush)算法过程prepare()，即首先将与s相连的边设为满流，并将这时产生的活动结点加入队列Q。这是算法的开始。以后便重复以下过程直到Q为空：(1).选出Q的一个活动顶点u。并依次判断残量网络G'中每条边(u,v)，若h(u)=h(v)+1，则顺着这里条边推流，直到Q变成非活动结点（不存在多余流量）。(Push推流过程)(2).如果u还是活动结点。则需要对u进行重新标号：h(u)=min{h(v)+1}，其中边(u,v)存在于G'中。然后再将u加入队列。(relable过程)可以证明，通过以上算法得到的结果就是最大流。预流推进算法示例顶点u的通过量g(u)：剩余图中，找入边权和与出边权和的较小值增广时，每次找一个通过量最小的点v，从点v向源点“推”大小为g(v)的流量向汇点“拉”大小为g(v)的流量尽量使剩余图中的边饱和34578g(u)=12用预流推进方法的一些网络流算法预流推进的算法核心思想是以边为单元进行推流操作：一般的预流推进算法：在剩余图中，维护一个预流，不断对活跃点执行push操作，或者relable操作来重新调整这个预流，直到不能操作。O(nm2)先进先出预流推进算法：在剩余图中，以先进先出队列维护活跃点。O(n3)最高标号预流推进算法HLLP：在剩余图中，每次检查最高标号的活跃点，需要用到优先队列。O(n2m1/2)费用流流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。右图是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。容易看出，此图的最大流（流量是8）为：fs1=f1t=5,fs2=f2t=3。所以它的费用是：3*5+4*5+7*3+2*3=62。(6,3)(5,4)(3,7)(8,2)STV1V2费用流问题费用流定义设有带费用的网络流图G=(V,E,C,W)，每条弧<Vi,Vj>对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：流量V(f)最大。满足a的前提下，流的费用Cost(f)=∑<i,j>∈E(fij*Wij)最小。 就称f是网络流图G的最小费用最大流。最小费用可改进路 设P是流f的可改进路，定义∑<vi,vj>∈P+Wij-∑<vi,vj>∈P-Wij

为P的费用(为什么如此定义？)

如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。费用流算法求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。算法可描述为：第1步.令f为零流。第2步.若无最小费用可改进路，转第5步；否则找到最小费用可改进路，设为P。第3步.根据P求delta（改进量）。第4步.放大f。转第2步。第5步.算法结束。此时的f即最小费用最大流。如何求最小费用可改进路设带费用的网络流图G=(V,E,C,W)，它的一个可行流是f。我们构造带权有向图B=(V’,E’)，其中：V’=V。若<Vi,Vj>∈E，fij<Cij，那么<Vi,Vj>∈E’，权为Wij。

若<Vi,Vj>∈E，fij>0，那么<Vj,Vi>∈E’，权为-Wij。显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。现在的问题变成：给定带权有向图B=(V’,E’)，求从S到T的一条最短路径。迭代法求最短路经考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法（SPFA算法）。设Short[i]表示从S到i顶点的最短路径长度；从S到顶点i的最短路径中，顶点i的前趋记为Last[i]。那么迭代算法描述如下：（为了便于描述，令n=|V’|，S的编号为0，T的编号为n+1）step1.令Short[i]

+∞（1≤i≤n+1），Short[0]

0。step2.遍历每一条弧<Vi,Vj>。若Short[i]+<i,j><Short[j]，则令Short[j]

Short[i]+<i,j>，同时Last[j]

i。重复做step2直到不存在任何任何弧满足此条件为止。step3.算法结束。若Short[n+1]=+∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。procedurecostflow;{求最小费用最大流}vari,j,x,delta:integer;best,last:tline;{best：最短路长度；last：可改进路中的前趋顶点}more:boolean;beginrepeatfillword(best,sizeof(best)shr1,maxint);fillchar(last,sizeof(last),0);last[1]:=maxint;best[1]:=0;{赋初值}repeatmore:=false;fori:=1tondoifbest[i]<>maxintthenforj:=1tondobeginif(flow[i,j]<limit[i,j])and(best[i]+cost[i,j]<best[j])thenbeginbest[j]:=best[i]+cost[i,j];last[j]:=i;more:=true;end;

if(flow[j,i]>0)and(best[i]-cost[j,i]<best[j])thenbeginbest[j]:=best[i]-cost[j,i];last[j]:=-i;more:=true;end;end;untilnotmore;{找最优可改进路}ifbest[n]=maxintthenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifx<deltathendelta:=x;untili=1;{求改进量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]>0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;untilfalse;{根据改进量放大流}end;思维发散与探索可改进路费用：“递增！递增？” 设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？迭代法：“小心死循环！嘿嘿……”

迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？费用：“你在乎我是负数吗？”容量：“我管的可不仅是弧。” 网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？有上下界的最大流前面我们已经了解了最大流问题，之中每条边(u,v)都有一个容量上界c(u,v)，而现在我们将这个问题再变一下，对于每条边又多了一个容量下界b(u,v)表示这条边至少要流low(u,v)这么多的流量。显然直接按照之前求最大流的方法，最后再判断每条边是否达到容量下界是。。。错滴！有上下界的最大流重新看下前面的例子在这个例子中，它的最大流为10，而如果直接用dinic或者SAP求出来会发现最大流为16且满足不了2→4这条边的容量下界。有上下界的最大流首先我们考虑某些图可能是不合法的，如下：

1→2至少要流3，而2→3最多只能流2.。所以我们首先要想办法判断一个图是否是合法滴。

有上下界的最大流这里介绍一种简易的方法来求解流量有上下界的网络中网络流问题:

AtFirst

c(u,v)

u到v的边的流量上界。

b(u,v)u到v的边流量下界。

st(u)

所有指向点u的边的下界之和。

ed(u)

点u指向其他点的所有边的下界之和。

s为源点，t为汇点。

有上下界的最大流Next构造一个新网络，设原网络为G，新的网络为D，D包含G中的所有点

构造D的方法如下：

1.加入虚拟源点vs和虚拟汇点vt

2.若边(u,v)属于G那么这条边也属于D， cnew(u,v)=c(u,v)-b(u,v)

3.对于G中的每一个点v，D中加入边 (vs,v),cnew(vs,v)=st(v)

4.对于G中的每一个点v，D中加入边(v,vt), cnew(v,vt)=ed(v)

5.加入边(t,s),cnew(t,s)=∞

6.tflow为所有边的下界的和

有上下界的最大流构图示例有上下界的最大流判断求出的最大流是否等于tflow，等于继续，否则该图不合法。在D中去掉所有和vs，vt相连的边，注意，这里面去掉边应是双向的都去掉，因为我们在更新网络时反向边的c也会变化。去掉t到s的附加边，注意这也应该是双向的。其他的边不要改变。

在这个去掉边之后的图中接着运行求