《最大流问题 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 实现的版本,虽然有点小错误,不可以直接使用。