最大流算法拓展.docx

网络最大流算法算法拓展一、网络最大流的算法分类：一、Ford-Fulkerson增广路方法1、 Ford-Fulkerson标号算法（最简单的实现）分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个点），检查与它连接的所有边，并进行扩展，直到扩展到t。2、最大容量增广路算法每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。3、Edmonds-Karp，最短路增广算法的BFS实现每次找一条最短的增广路，BFS是一个可以很方便的实现思想。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、重标记与前移算法维护一个队列，对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。3、最高标号预留与推进算法记录d值，然后优先处理d值较高的，直至没有盈余。二、网络最大流的算法实现一、Edmonds-Karp（EK）算法就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)，Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的 Dinic 算法都属于此。SAP 类算法可统一描述如下：Shortest Augmenting Path{ x -- 0while 在残量网络 Gx 中存在增广路 s ~ t do { 找一条最短的增广路径 P delta -- min{rij:(i,j) 属于 P}沿 P 增广 delta 大小的流量更新残量网络 Gx }return x }在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索 (BFS)，E-K 算法就直接来源于此。每次用一遍 BFS 寻找从源点 s 到终点 t 的最短路作为增广路径，然后增广流量 f 并修改残量网络，直到不存在新的增广路径。E-K 算法的时间复杂度为 O(V*E^2)，由于 BFS 要搜索全部小于最短距离的分支路径之后才能找到终点，因此可以想象频繁的 BFS 效率是比较低的。实践中此算法使用的机会较少。代码如下：#define VMAX 201int n, m; //分别表示图的边数和顶点数int c[VMAX][VMAX]; //容量int Edmonds_Karp( int s, int t ) //输入源点和汇点{ int p, q, queue[VMAX], u, v, pre[VMAX], flow= 0, aug;while(true){ memset(pre,-1,sizeof(pre)); //记录父节点 for( queue[p=q=0]=s; p=q; p++ ) //广度优先搜索{u= queue[p]; for( v=0; vmpre[t]0; v++ ) if( c[u][v]0 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]aug) aug=c[u][v]; for( u=pre[v=t]; v!=s; v=u,u=pre[u] ) c[u][v]-=aug, c[v][u]+=aug; flow+= aug; } return flow;}//0 至 n-1二、Ford-Fulkerson方法每次找增广路，把这条路上的所有点的流量加上这条路上的残余容量，再找新的增广路，直到找不到为止。Ford_Fulkerson( G,