最近在看网络流，把几个常用的算法总结下，正确性的证明和一些理论的东西就不写了，参看算法导论和神牛们的论文，我只写算法的理解和实现模板。
Ford-Fulkerson方法
每次找增广路，把这条路上的所有点的流量加上这条路上的残余容量，再找新的增广路，直到找不到为止，它有很多种实现方法，下面给出算法导论上的伪代码
Ford_Fulkerson( G, s, t ){
for each edge( u, v )∈E[G]
do f[u,v]= 0
f[v,u]= 0
while there exists a path p from s to t in the residual network Gf
do Cf(p)= min{ Cf(u,v) | (u,v) is in p }
for each edge(u,v) in p
do f[u,v]+= Cf(p)
f[v,u]= -f[u,v]Edmonds-Karp算法
就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE
2)
(代码参考NOCOW)
#define VMAX 201
int n, m; //分别表示图的边数和顶点数
int c[VMAX][VMAX];
int Edmonds_Karp( int s, int t ){ //输入源点和汇点
int p, q, queue[VMAX], u, v, pre[VMAX], flow= 0, aug;
while(true){
memset(pre,-1,sizeof(pre)); //记录父节点
for( queue[p=q=0]=s; p<=q; p++ ){ //广度优先搜索
u= queue[p];
for( v=0; v<m&&pre[t]<0; v++ )
if( c[u][v]>0 && pre[v]<0 )
pre[v]=u, queue[++q]=v;
if( pre[t]>=0 ) break;
}
if( pre[t]<0 ) break; //不存在增广路
aug= 0x7fff; //记录最小残留容量
for( u=pre[v=t]; v!=s; v=u,u=pre[u] )
if(c[u][v]<aug) aug=c[u][v];
for( u=pre[v=t]; v!=s; v=u,u=pre[u] )
c[u][v]-=aug, c[v][u]+=aug;
flow+= aug;
}
return flow;
}Push-Relabel算法
Relabel-to-Front算法
Preflow-Push算法
Dinic算法
先放着，慢慢写……
http://evalls.yo2.cn/articles/preflow_push.htmlhttp://www.stubc.com/thread-3665-1-1.htmlhttp://cuitianyi.com/blog/%E6%B1%82%E6%9C%80%E5%A4%A7%E6%B5%81%E7%9A%84relabel-to-front%E7%AE%97%E6%B3%95/http://blog.sina.com.cn/s/blog_5774b8650100cnjc.htmlhttp://www.nocow.cn/index.php/%E7%BD%91%E7%BB%9C%E6%B5%81#.E7.BB.83.E4.B9.A0.E9.A2.98.E7.9B.AEhttp://hi.baidu.com/_green_hand_/blog/item/0d1715250b6f5435c9955917.htmlhttp://blog.csdn.net/soberman/archive/2009/03/09/3974871.aspx
posted on 2009-06-23 21:08
古月残辉 阅读(3754)
评论(0) 编辑 收藏 引用 所属分类:
Theory