最大流算法小结

《最大流算法小结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、网络最大流的算法网络最大流的算法分类：一、Ford-Fulkerson增广路方法1、Ford-Fulkerson标号算法（最简单的实现）分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个点），检查与它连接的所有边，并进行扩展，直到扩展到t。2、最大容量增广路算法每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。3、Edmonds-Karp，最短路增广算法的BFS实现每次找一条最短的增广路，BFS是一个可以很方便的实现思

2、想。4、距离标号算法最短路增广的O(n)寻找实现，使用距离函数d：d[t]=0;d<=d[j]+1若存在(i,j)∈E；只有路径上满足d=d[i+1]+1的增广路才为满足要求的，一开始我们初始化使标号恰好满足要求，之后不断更改标号使其可以使增广继续。5、Dinic，分层思想对网络分层（按照距t的距离），保留相邻层之间的边，然后运用一次类似于距离标号的方法（其实质是DFS）进行增广。二、预留与推进算法1、一般性算法随便找个点，要么将他的盈余推出去，要么对他进行重标记，直至无活跃点为止。2、重标记与前移算法维护一个队列，

3、对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。3、最高标号预留与推进算法记录d值，然后优先处理d值较高的，直至没有盈余。网络最大流的算法实现一、Edmonds-Karp（EK）算法就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)，ShortestAugmentingPath(SAP)是每次寻找最短增广路的一类算法，Edmonds-Karp算法以及后来著名的Dinic算法都属于此。SAP类算法可统一描

4、述如下：ShortestAugmentingPath{x<--0while在残量网络Gx中存在增广路s~>tdo{找一条最短的增广路径Pdelta<--min{rij:(i,j)属于P}沿P增广delta大小的流量更新残量网络Gx}returnx}在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索(BFS)，E-K算法就直接来源于此。每次用一遍BFS寻找从源点s到终点t的最短路作为增广路径，然后增广流量f并修改残量网络，直到不存在新的增广路径。E-K算法的时间复杂度为O(V*E^2)，由于BFS要搜索全部小于

5、最短距离的分支路径之后才能找到终点，因此可以想象频繁的BFS效率是比较低的。实践中此算法使用的机会较少。代码如下：#defineVMAX201intn,m;//分别表示图的边数和顶点数intc[VMAX][VMAX];//容量intEdmonds_Karp(ints,intt)//输入源点和汇点{intp,q,queue[VMAX],u,v,pre[VMAX],flow=0,aug;while(true){memset(pre,-1,sizeof(pre));//记录父节点for(queue[p=q=0]=s;p<=

6、q;p++)//广度优先搜索{u=queue[p];for(v=0;v0&&pre[v]<0)pre[v]=u,queue[++q]=v;if(pre[t]>=0)break;}if(pre[t]<0)break;//不存在增广路aug=0x7fff;//记录最小残留容量for(u=pre[v=t];v!=s;v=u,u=pre[u])if(c[u][v]

7、[v]-=aug,c[v][u]+=aug;flow+=aug;}returnflow;}//0至n-1二、Ford-Fulkerson方法每次找增广路，把这条路上的所有点的流量加上这条路上的残余容量，再找新的增广路，直到找不到为止，它有很多种实现方法，下面给出算法导论上的伪代码。Ford_Fulkerson(G,s,t){foreachedge(u,v)∈E[G]dof[u,v]=0f[v,u]=0whilethereexistsapathpfromstotintheresidualnetworkGfdoCf(p)

8、=min{Cf(u,v)

9、(u,v)isinp}foreachedge(u,v)inpdof[u,v]+=Cf(p)f[v,u]=-f[u,v]Ford_Fulkerson算法求解PKU1273代码1：#include#includeusingnamespacestd;constintmaxN=201;stat