《最大流问题 edmonds-karp算法》由会员分享，可在线阅读，更多相关《最大流问题 edmonds-karp算法（7页珍藏版）》请在金锄头文库上搜索。
1、最大流问题最大流问题 Edmonds-KarpEdmonds-Karp 算法算法迭代优化最大流问题 Edmonds-Karp 算法（附 POJ 1273 解题）2009 年 06 月 27 日 星期六 22:36 图论中的最大流问题解法一般分为两类：（1）增广路径方法。这个方法是由 Ford-Fulkerson 俩人提出来的，所以这一类的方法统称 Ford-Fulkerson 算法。增广路径又叫流量增益路径，增广的意思我个人理解是“可扩张的” ，是由多条边。这种方法总体思想是先找到一条从源点到汇点的增广路径，这条路径不管由多少条边组成，这条路径的容量只能是其中容量最小的边的容量。这其实就是桶的
2、短板效应（我的理解是在图论中也就是最大流最小割定理） 。如果我们能找到所有这样的路径（路径是可部分重叠的） ，那么最后一定能得到最大流。 （证明就是最大流最小割定理） 。当然，我们每找到一条之后，图其实是发生了一些变化的，我们必须做出一定的标记。所以这个算法不仅有迭代优化的思想（最大流算法实际上是线性规划的一种） ，也有标记的思想。此类算法的不同之处在于找到所有增广路径的方法不同：Edmonds-Karp 算法（下面简称 EK 算法）使用 BFS（广度优先搜索） ；Dinic算法使用 DFS 和层次图。（2）预流法。我还没有看。 。 。主要包括：Push-relabel/Relabel-to-
3、front/SAP 算法等。关于网络流问题，很多算法书上采用的讲解方式不尽相同。例如数据结构与算法分析 C+描述 （第三版中文版）中就采用的是残余图的方法，只讲了基本的 Ford-Fulkerson 方法，既无伪代码，又无具体的路径寻找方法；算法设计与分析基础 （第二版中文版）采用了正向边和反向边结合的讲解，如果能同时对照残余图的思想则更好，而且此书还给出了 EK 算法的伪代码和算法思想。因此个人推荐后者作为参考书，本文中的代码也是基于 EK 算法的。（一）如何确定一条路径的流量：标号法根据 EK 算法，路径上的每个点都需要两个标记：一个标记从源点到当前节点实际还剩多少流量可用；另一个标记在这
4、条路径上当前节点的前驱。下面解释一下这两个标记，设当前节点下标为 j，其第一个标记我们设为 flowj。其前驱节点下标为 i，其标记为 flowi。另外设i 与 j 之间的边的容量为 x。它们二者的关系遵循以下的公式：flowj = min( flowi, x)这是为什么呢？我们定性的讨论一下。节点 j 的流量肯定通过边ij，来自于其前驱的节点 i 的。如果边的容量 x 大于节点 i 的流量，那么边 ij 并不能被充满；如果边的容量 x 小于节点 i 的流量，那么这些流量也不能全部经过边 ij 进入节点 j。所以节点 j 的流量只能取其二者中更小的。那么我们经过从源点到汇点的这种迭代（有点动态
5、规划的意思：一个状态只跟其前一个状态有关系） ，最终就得到了这条路径上最小的流量（被短板限制的流量） 。（二）为什么要有反向边或者残余图？前面我们确定了一条路径的最小流量之后，我们实际上可以把这部分流量从图中删去（这个可以看做减治的过程）：因为这个路径以后是不会更改的，而且路径之间互不影响。但是也会出现一定的问题：结果往往不是最优的。反向边和残余图可以解决这一问题（但是其证明极其复杂） 。（三）找到所有的路径我们知道一次 BFS 或者 DFS 就能保证我们能找到图上所有的从源点到汇点的路径。这个就不再多说了。（四）EK 算法代码（实际上是 POJ 1273 题的解答）题目见：http:/ PO
6、J 的题目写的，如果挪作它用，还得改写一些地方。1 /*2 author : MicroGrape3 question : POJ 1273 Drainage Ditches4 category : network max flow5 */6 7 #include 8 #include 9 10 using namespace std;11 12 const int NODES = 210;13 const int INF = 0x7FFFFFFF;14 15 /the flow network16 int capacityNODESNODES;17 /record flows from on
7、e vertex to next18 int flowNODES;19 /record the previous node in the temporary path20 /if previ != -1,means its visited.21 int prevNODES;22 /number of nodes in fact23 int num;24 25 /use Breadth First Search to find an augment path26 int BFS(int src, int dest)27 28 queue next;29 while(!next.empty()30
8、 next.pop();31 32 for( int i = 0; i 0 54 next.push(j);55 prevj = index;/record the path56 57 58 59 /not reach destination point60 if(prevdest = -1)61 return -1;62 /return the minimum flow increment63 return flownum;64 65 66 /key function67 int maxflow(int src, int dest)68 69 int max_flow = 0;70 71 i
9、nt increment = 0;72 while( ( increment = BFS(src, dest) ) != -1)73 74 max_flow += increment;75 76 int k = dest;77 while( k != src)78 79 int last = prevk;80 /key step: update the flow, iteratively81 capacitylastk -= increment;/decrease the forward edge82 capacityklast += increment;/add an opposite ed
10、ge83 k = last;84 85 86 return max_flow;87 88 89 int main()90 91 /input the first line92 int edges ;93 while( cinedgesnum )94 95 /input each edge96 int u, v, value;97 memset( capacity, 0, sizeof(capacity) );98 for(int i = 0 ; i uvvalue;101 if( u = v )102 continue;103 capacityuv += value;104 105 coutmaxflow(1, num)endl;106 107 108 return 0;109 110 附：参考资料网上的资料比较芜杂，代码往往没有注释。但 http:/ 给出了一个比较清晰的 java 实现的版本，虽然有点小错误，不可以直接使用。
