最大流问题 Edmonds-Karp算法.docVIP

最大流问题 Edmonds-Karp算法 [迭代优化]最大流问题 Edmonds-Karp算法（附POJ 1273解题）2009年06月27日 星期六 22:36图论中的最大流问题解法一般分为两类： （1）增广路径方法。这个方法是由Ford-Fulkerson俩人提出来的，所以这一类的方法统称Ford-Fulkerson算法。增广路径又叫流量增益路径，增广的意思我个人理解是“可扩张的”，是由多条边。 这种方法总体思想是先找到一条从源点到汇点的增广路径，这条路径不管由多少条边组成，这条路径的容量只能是其中容量最小的边的容量。这其实就是桶的短板效应（我的理解是在图论中也就是最大流最小割定理）。如果我们能找到所有这样的路径（路径是可部分重叠的），那么最后一定能得到最大流。（证明就是最大流最小割定理）。当然，我们每找到一条之后，图其实是发生了一些变化的，我们必须做出一定的标记。所以这个算法不仅有迭代优化的思想（最大流算法实际上是线性规划的一种），也有标记的思想。 此类算法的不同之处在于找到所有增广路径的方法不同：Edmonds-Karp算法（下面简称EK算法）使用BFS（广度优先有哪些信誉好的足球投注网站）；Dinic算法使用DFS和层次图。 （2）预流法。我还没有看。。。主要包括：Push-relabel/Relabel-to-front/SAP算法等。 关于网络流问题，很多算法书上采用的讲解方式不尽相同。例如《数据结构与算法分析C++描述》（第三版中文版）中就采用的是残余图的方法，只讲了基本的Ford-Fulkerson方法，既无伪代码，又无具体的路径寻找方法；《算法设计与分析基础》（第二版中文版）采用了正向边和反向边结合的讲解，如果能同时对照残余图的思想则更好，而且此书还给出了EK算法的伪代码和算法思想。因此个人推荐后者作为参考书，本文中的代码也是基于EK算法的。 （一）如何确定一条路径的流量：标号法 根据EK算法，路径上的每个点都需要两个标记：一个标记从源点到当前节点实际还剩多少流量可用；另一个标记在这条路径上当前节点的前驱。 下面解释一下这两个标记，设当前节点下标为j，其第一个标记我们设为flow[j]。其前驱节点下标为i，其标记为flow[i]。另外设i与j之间的边的容量为x。 它们二者的关系遵循以下的公式： flow[j] = min( flow[i], x) 这是为什么呢？我们定性的讨论一下。节点j的流量肯定通过边ij，来自于其前驱的节点i的。如果边的容量x大于节点i的流量，那么边ij并不能被充满；如果边的容量x小于节点i的流量，那么这些流量也不能全部经过边ij进入节点j。所以节点j的流量只能取其二者中更小的。 那么我们经过从源点到汇点的这种迭代（有点动态规划的意思：一个状态只跟其前一个状态有关系），最终就得到了这条路径上最小的流量（被短板限制的流量）。 （二）为什么要有反向边或者残余图？ 前面我们确定了一条路径的最小流量之后，我们实际上可以把这部分流量从图中删去（这个可以看做减治的过程）：因为这个路径以后是不会更改的，而且路径之间互不影响。但是也会出现一定的问题：结果往往不是最优的。反向边和残余图可以解决这一问题（但是其证明极其复杂）。 （三）找到所有的路径 我们知道一次BFS或者DFS就能保证我们能找到图上所有的从源点到汇点的路径。这个就不再多说了。 （四）EK算法代码（实际上是POJ 1273题的解答） 题目见：/JudgeOnline/problem?id=1273 本代码仅针对POJ的题目写的，如果挪作它用，还得改写一些地方。 1 /* 2 author : MicroGrape 3 question : POJ 1273 Drainage Ditches 4 category : network max flow 5 */ 6 7 #include iostream 8 #include queue 9 10 using namespace std; 11 12 const int NODES = 210; 13 const int INF = 0x7FFFFFFF; 14 15 //the flow network 16 int capacity[NODES][NODES]; 17 //record flows from one vertex to next 18 int flow[NODES]; 19 //record the previous node in the temporary path 20 //if prev[i] != -1,means its visited. 21 int prev[NODES]; 22 //number of nodes in