图的匹配问题与最大流问题（三）――最大流问题Ford-Fulkerson方法Java实现 - smartxxyx的专栏 - 博客频道 - CSDN.NET

上篇文章主要介绍了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）

Read full article from 图的匹配问题与最大流问题（三）――最大流问题Ford-Fulkerson方法Java实现 - smartxxyx的专栏 - 博客频道 - CSDN.NET