上篇文章主要介绍了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;
}
}
return result; } public static double[][] getResidualNetwork() { return residualNetwork; } public static double[][] getFlowNetwork() {
return flowNetwork;
} }