[转]Ford-Fulkerson求解最大流

YUI posted @ 2010年11月06日 02:18 in 未分类 , 1628 阅读

 

在算法导论中对求解最大流问题给出了一般性的解决方法,但并没有涉及到具体的实现。在这里我还是重新的对求解最大流的思想进行一般性的描述,然后再给出具体的实现。

      Ford-Fulkerson方法依赖于三种重要思想,这三个思想就是在上一篇网络流基础中提到的:残留网络,增广路径和割。Ford-Fulkerson方法是一种迭代的方法。开始时,对所有的u,v∈V有f(u,v)=0,即初始状态时流的值为0。在每次迭代中,可通过寻找一条“增广路径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直至增广路径都被找出来,根据最大流最小割定理,当不包含增广路径时,f是G中的一个最大流。在算法导论中给出的Ford-Fulkerson实现代码如下:

     FORD_FULKERSON(G,s,t)
     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]                //对于反向的边,根据反对称性求

     第1~3行初始化各条边的流为0,第4~8就是不断在残留网络Gf中寻找增广路径,并沿着增广路径的方向更新流的值,直到找不到增广路径为止。而最后的最大流也就是每次增加的流值cf(p)之和。在实际的实现过程中,我们可以对上述代码做些调整来达到更好的效果。如果我们采用上面的方法,我们就要保存两个数组,一个是每条边的容量数组c,一个就是上面的每条边的流值数组f,在增广路径中判断顶点u到v是否相同时我们必须判断c[u][v]-f[u][v]是否大于0,但是因为在寻找增广路径时是对残留网络进行查找,所以我们可以只保存一个数组c来表示残留网络的每条边的容量就可以了,这样我们在2~3行的初始化时,初始化每条边的残留网络的容量为G的每条边的容量(因为每条边的初始流值为0)。而更新时,改变7~8行的操作,对于在残留网络上的边(u,v)执行c[u][v]-=cf(p),而对其反向的边(v,u)执行c[v][u]+=cf(p)即可。

      现在剩下的最关键问题就是如何寻找增广路径。而Ford-Fulkerson方法的运行时间也取决于如何确定第4行中的增广路径。如果选择的方法不好,就有可能每次增加的流非常少,而算法运行时间非常长,甚至无法终止。对增广路径的寻找方法的不同形成了求最大流的不同算法,这也是Ford-Fulkerson被称之为“方法”而不是“算法”的原因。下面将给出Ford-Fulkerson方法的具体实现细节:

int c[MAX][MAX];  //残留网络容量
int pre[MAX];  //保存增广路径上的点的前驱顶点
bool visit[MAX];

int Ford_Fulkerson(int src,int des,int n){   //src:源点 des:汇点 n:顶点个数
     int i,_min,total=0;
     while(true){
         if(!Augmenting_Path(src,des,n))return total; //如果找不到增广路就返回,在具体实现时替换函数名
         _min=(1<<30);
         i=des;
         while(i!=src){   //通过pre数组查找增广路径上的边,求出残留容量的最小值
             if(_min>c[pre[i]][i])_min=c[pre[i]][i];
             i=pre[i];
         }
         i=des;
         while(i!=src){    //再次遍历,更新增广路径上边的流值
             c[pre[i]][i]-=_min;
             c[i][pre[i]]+=_min;
             i=pre[i];
         }
         total+=_min;     //每次加上更新的值
     }
}

 


 

Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的p的计算,代码如下:

bool Edmonds_Karp(int src,int des,int n){
     int v,i;
     for(i=0;i<n;i++)visit[i]=false;
     front=rear=0;     //初始化
     que[rear++]=src;
     visit[src]=true;
     while(front!=rear){     //将源点进队后开始广搜的操作
         v=que[front++]; 
         
//这里如果采用邻接表的链表实现会有更好的效率,但是要注意(u,v)或(v,u)有任何一条
         //边存在于原网络流中,那么邻接表中既要包含(u,v)也要包含(v,u)

         for(i=0;i<n;i++){ 
             if(!visit[i]&&c[v][i]){  
//只有残留容量大于0时才存在边
                 que[rear++]=i;
                 visit[i]=true;
                 pre[i]=v;
                 if(i==des)return true;   //如果已经到达汇点,说明存在增广路径返回true
             }
         }
     }
     return false;
}


现在先给出一个最基本的EK实现,以后会陆续将其他算法实现添加上来O(∩_∩)O~

KVS 4th Class Questi 说:
2022年9月29日 21:13

Kendriya Vidyalaya Sangathan Class 4th Standard Student can download the Model Paper in subject wise for all regional students in medium wise for the Elementary Education Primary School practice model question bank with answer solutions for Term-1, Term-2, Term-3, Term-4 exams conducted under the board and school level. KVS 4th Class Question Paper Kendriya Vidyalaya Sangathan Class 4th Standard Student can download the Model Paper in subject wise for all regional students in medium wise for the Elementary Education Primary School practice model question bank with answer solutions for Term-1, Term-2, Term-3, Term-4 exams conducted under the board and school level.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter