图的匹配问题与最大流问题（三）最大流问题Ford-Fulkerson方法Java实现

图的匹配问题与最大流问题（三）最大流问题Ford-Fulkerson方法Java实现2015-09-02上篇文章主要介绍了Ford-Fulkerson方法的理论基础，本篇给出一种Java的实现。

先借助伪代码熟悉下流程

FORD-FULKERSON（G，t，s）

1 for each edge（u,v）属于E（G）

2 do f[u,v]=0

3 f[v,u]=0

4 while there exists a path p from s to t in the residual network Gf

5 do cf（p）=min{cf（u,v）:（u,v）is in p}

6 for each edge （u,v） in p

7 do f[u,v]=f[u,v]+cf（p）

8 f[v,u]=-f[u,v]

如果在4行中用广度优先搜索来实现对增广路径p的计算，即找到s到t的最短增广路径，能够改进FORD-FULERSON的界，这就是Ford-Fulkerson方法的Edmonds-Karp算法

证明该算法的运行时间为O（VE*E），易知，对流增加的全部次数上界为O（VE），每次迭代时间O（E）

package maxflow;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;import util.EdgeUtil;import util.NodeUtil;import entry.Edge;import entry.Node;/*** Ford Fulkerson方法求最大流，这是一种迭代的方法，开始是，初始流为0，每次迭代中，课通过寻找一条增广路径来增加流值。反复进行这一过程，直至找不到任何增广路径* 本算法使用了Edmonds-Karp算法（一种对Ford Fulkerson方法的实现），在寻找增广路径时使用了寻找s到t的最短路径的方法。复杂度O（VE2）* @author xhw**/public class FordFulkerson {private static double residualNetwork[][]=null;private static double flowNetwork[][]=null;/*** @param args*/public static void main（String[] args） {double graph[][]={{0,16,13,0,0,0},{0,0,10,12,0,0},{0,4,0,0,14,0},{0,0,9,0,0,20},{0,0,0,7,0,4},{0,0,0,0,0,0}};System.out.println（edmondsKarpMaxFlow（graph,0,5））;}/*** 实现FordFulkerson方法的一种算法——edmondsKarp算法* @param graph* @param s* @param t* @return*/public static double edmondsKarpMaxFlow（double graph[][],int s,int t）{int length=graph.length;//List<Node> nodeList=NodeUtil.generateNodeList（graph）;double f[][]=new double[length][length];for（int i=0;i<length;i++）{for（int j=0;j<length;j++）{f[i][j]=0;}}double r[][]=residualNetwork（graph,f）;Node result=augmentPath（r,s,t）;double sum=0;while（result！=null）{double cfp=0;cfp=minimumAugment（r,result）;//说明已经没有增广路径了if（cfp==0）{break;}while（result.getParent（）！=null）{Node parent=result.getParent（）;f[parent.nodeId][result.nodeId]+=cfp;f[result.nodeId][parent.nodeId]=-f[parent.nodeId][result.nodeId];result=parent;}sum+=cfp;r=residualNetwork（graph,f）;result=augmentPath（r,s,t）;}residualNetwork=r;flowNetwork=calculateFlowNetwork（graph,r）;/*for（int i=0;i<length;i++） { for（int j=0;j<length;j++） {System.out.print（（flowNetwork[i][j]>0？flowNetwork[i][j]:0.0）+" "）; } System.out.println（）; }*/return sum;}/*** 计算最终的流网络，也就是最大流网络* @param graph* @param r* @return*/private static double[][] calculateFlowNetwork（double[][] graph, double[][] r） {int length=graph.length;double f[][]=new double[graph.length][graph.length];for（int i=0;i<length;i++）{for（int j=0;j<length;j++）{f[i][j]=graph[i][j]-r[i][j];}}return f;}/*** 确定增广路径可扩充的流值* @param graph* @param result* @return*/public static double minimumAugment（double graph[][],Node result）{double cfp=Double.MAX_VALUE;while（result.getParent（）！=null）{Node parent=result.getParent（）;double weight=graph[parent.nodeId][result.nodeId];if（weight<cfp&&weight>0）{cfp=weight;}else if（weight<=0）{cfp=0;break;}result=parent;}return cfp;}/*** 计算残余网络* @param c* @param f* @return*/private static double[][] residualNetwork（double c[][],double f[][]） {int length=c.length;double r[][]=new double[length][length];for（int i=0;i<length;i++）{for（int j=0;j<length;j++）{r[i][j]=c[i][j]-f[i][j];}}return r;}/*** 广度优先遍历，寻找增光路径，也是最短增广路径* @param graph* @param s* @param t* @return*/public static Node augmentPath（double graph[][],int s,int t）{Node result=null;List<Node> nodeList=NodeUtil.generateNodeList（graph）;nodeList.get（s）.distance=0;nodeList.get（s）.state=1;Queue<Node> queue=new LinkedList<Node>（）;queue.add（nodeList.get（s））;while（！queue.isEmpty（））{Node u=queue.poll（）;for（Node n:u.getAdjacentNodes（））{if（n.state==0）{n.state=1;n.distance=u.distance+1;n.setParent（u）;queue.add（n）;}}u.state=2;if（u.nodeId==t）{result=u;break;}}returnresult;}public static double[][] getResidualNetwork（） {return residualNetwork;}public static double[][] getFlowNetwork（） {return flowNetwork;}}

作者：csdn博客 smartxxyx