上篇文章，主要介绍了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;
}
}
上面的实现有点麻烦，给出一个简化版本，效率也提高了一些。
class FordFulkerson
{
private double residualNetwork[][]=null;
private double flowNetwork[][]=null;
public final int N;
int parent[];
public FordFulkerson(int N)
{
this.N=N;
parent=new int[N];
}
/**
* 实现FordFulkerson方法的一种算法——edmondsKarp算法
* @param graph
* @param s
* @param t
* @return
*/
public double edmondsKarpMaxFlow(double graph[][],int s,int t)
{
int length=graph.length;
double f[][]=new double[length][length];
for(int i=0;i<length;i++)
{
Arrays.fill(f[i], 0);
}
double r[][]=residualNetwork(graph,f);
double result=augmentPath(r,s,t);
double sum=0;
while(result!=-1)
{
int cur=t;
while(cur!=s)
{
f[parent[cur]][cur]+=result;
f[cur][parent[cur]]=-f[parent[cur]][cur];
r[parent[cur]][cur]-=result;
r[cur][parent[cur]]+=result;
cur=parent[cur];
}
sum+=result;
result=augmentPath(r,s,t);
}
residualNetwork=r;
flowNetwork=f;
return sum;
}
/**
* deepCopy
* @param c
* @param f
* @return
*/
private 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 double augmentPath(double graph[][],int s,int t)
{
double maxflow=Integer.MAX_VALUE;
Arrays.fill(parent, -1);
Queue<Integer> queue=new LinkedList<Integer>();
queue.add(s);
parent[s]=s;
while(!queue.isEmpty())
{
int p=queue.poll();
if(p==t)
{
while(p!=s)
{
if(maxflow>graph[parent[p]][p])
maxflow=graph[parent[p]][p];
p=parent[p];
}
break;
}
for(int i=0;i<graph.length;i++)
{
if(i!=p&&parent[i]==-1&&graph[p][i]>0)
{
//flow[i]=Math.min(flow[p], graph[p][i]);
parent[i]=p;
queue.add(i);
}
}
}
if(parent[t]==-1)
return -1;
return maxflow;
}
public double[][] getResidualNetwork() {
return residualNetwork;
}
public double[][] getFlowNetwork() {
return flowNetwork;
}
}