2023年7月29日发(作者：)

⽹络流-最⼤流EdmondKarp算法详细讲解以及java实现源代码最⼤流的含义，就是说从源点到经过的所有路径的最终到达汇点的所有流量和。1. EK算法的核⼼：反复寻找源点s到汇点t之间的增⼴路径（路径上的最⼩边值就是可以⽤过路径的最⼤流量)，每找到⼀条路径,我们正向减去对应边的流量，并且反向增加流量（主要是因为路径是随机选取的，使⽤贪婪算法可能获取的是局部最优解，添加反向边可以解除原来的错误决定。如果要做到这个，我们需要记录路径中每个点的前驱结点），最后我们获得所有可以通过的路径的和就是所能够得到的最⼤流。2.算法举例举个例⼦吧（参考⽂章开始所给的⽹址内容）：求源点1，到汇点4的最⼤流

⾸先，我们找到第⼀条路径1-4 路径流为20我们对应边需要减去流量，并且添加⽅向便1-4的流量基于上⼀个图，我们继续查找从源点1到汇点4的路径。我们找到1-2-4 路径，流量为20，减去正向边，增加反向边继续下⼀步，找到1-2-3-4路径，流量为10这个就是最终的图，因为找不到1-4的路径了3.算法分析接下来，解释⼀下为什么需要添加⽅向边：

我们第⼀次找到了1-2-3-4这条增⼴路，这条路上的delta值显然是1。于是我们修改后得到了下⾯这个流。（图中的数字是容量）

这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增⼴路了，当前的流量是1。但这个答案明显不是最⼤流，因为我们可以同时⾛1-2-4和1-3-4，这样可以得到流量为2的流。那么我们刚刚的算法问题在哪⾥呢？问题就在于我们没有给程序⼀个”后悔”的机会，应该有⼀个不⾛(2-3-4)⽽改⾛(2-4)的机制。那么如何解决这个问题呢？回溯搜索吗？那么我们的效率就上升到指数级了。⽽这个算法神奇的利⽤了⼀个叫做反向边的概念来解决这个问题。即每条边(I,j)都有⼀条反向边(j,i)，反向边也同样有它的容量。我们直接来看它是如何解决的：在第⼀次找到增⼴路之后，在把路上每⼀段的容量减少delta的同时，也把每⼀段上的反⽅向的容量增加delta。即在Dec(c[x,y],delta)的同时，inc(c[y,x],delta)我们来看刚才的例⼦，在找到1-2-3-4这条增⼴路之后，把容量修改成如下这时再找增⼴路的时候，就会找到1-3-2-4这条可增⼴量，即delta值为1的可增⼴路。将这条路增⼴之后，得到了最⼤流2。

那么，这么做为什么会是对的呢？我来通俗的解释⼀下吧。事实上，当我们第⼆次的增⼴路⾛3-2这条反向边的时候，就相当于把2-3这条正向边已经是⽤了的流量给”退”了回去，不⾛2-3这条路，⽽改⾛从2点出发的其他的路也就是2-4。（有⼈问如果这⾥没有2-4怎么办，这时假如没有2-4这条路的话，最终这条增⼴路也不会存在，因为他根本不能⾛到汇点）同时本来在3-4上的流量由1-3-4这条路来”接管”。⽽最终2-3这条路正向流量1，反向流量1，等于没有流量。源代码import .*;import ;public class EdmodKarp { int maxdata=_VALUE; int[][] capacity; int[] flow; int[] pre; int n; Queue queue; public EdmodKarp(int[][] capacity) { ty=capacity; this.n=; =new int[n]; } //⼴度优先遍历的查找⼀条src到des的路径 int BFS(int src,int des) { int i; =new LinkedList(); =new int[n]; for(i=0;i0 && pre[i]==-1) { pre[i] = index; //记录前驱 flow[i] = (capacity[index][i],flow[index]); //关键：迭代的找到增量 (i); } } } if(pre[des]==-1) //残留图中不再存在增⼴路径 return -1; else return flow[des];

}

int maxFlow(int src,int des) { int increasement= 0; int sumflow = 0; while((increasement=BFS(src,des))!=-1) {

int k = des; //利⽤前驱寻找路径 while(k!=src) { int last = pre[k]; capacity[last][k] -= increasement; //改变正向边的容量 capacity[k][last] += increasement; //改变反向边的容量 k = last; } n("-------改变后---------"); for(int j=0;j

public static void main(String args[]) { int[][] matrix=new int[4][4]; matrix[0][1]=4; matrix[0][3]=2; matrix[1][2]=3; matrix[1][3]=2; matrix[2][3]=1;

EdmodKarp edm=new EdmodKarp(matrix); n("-------初始化---------"); for(int j=0;j

}