查看: 8548|回复: 1

[问题求助] Ford-Fulkerson算法计算如下网络中的最大流

字体大小: 正常放大

6 主题	7 听众	140 积分

升级 20%

TA的每日心情

	郁闷 2014-2-7 13:28

签到天数: 47 天

[LV.5]常住居民I

自我介绍: 好好学习，天天向上。

电梯直达

1^#

发表于 2013-1-20 17:38 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

用Ford-Fulkerson算法计算如下网络中的最大流，每条弧上的两个数字分别表示容量和当前流量。

编写程序如下：
clc,clear,M=1000;
u(1,2)=1;u(1,3)=1;u(1,4)=2;
u(2,3)=1;u(2,5)=2;
u(3,5)=1;
u(4,3)=3;u(4,5)=3;
f(1,2)=1;f(1,3)=0;f(1,4)=1;
f(2,3)=0;f(2,5)=1;
f(3,5)=1;
f(4,3)=1;f(4,5)=0;
n=length(u);
list=[];
maxf=zeros(1:n);maxf(n)=1;
while maxf(n)>0
maxf=zeros(1,n);pred=zeros(1,n);
list=1;record=list;maxf(1)=M;
while (~isempty(list))&(maxf(n)==0)
   flag=list(1);list(1)=[];
   index1=(find(u(flag,:)~=0));
   label1=index1(find(u(flag,index1)...
   -f(flag,index1)~=0));
   label1=setdiff(label1,record);
   list=union(list,label1);
   pred(label1(find(pred(label1)==0)))=flag;
   maxf(label1)=min(maxf(flag),u(flag,label1)...
   -f(flag,label1));
   record=union(record,label1);
   label2=find(f(:,flag)~=0);
   label2=label2';
   label2=setdiff(label2,record);
   list=union(list,label2);
   pred(label2(find(pred(label2)==0)))=-flag;
   maxf(label2)=min(maxf(flag),f(label2,flag));
   record=union(record,label2);
end
   if maxf(n)>0
      v2=n;
      v1=pred(v2);
      while v2~=1
         if v1>0
            f(v1,v2)=f(v1,v2)+maxf(n);
         else
         v1=abs(v1);
         f(v2,v1)=f(v2,v1)-maxf(n);
         end
      v2=v1;
      v1=pred(v2);
      end
   end
end
f
我想知道这个程序中：

1.什么是当前流量？这个应该不是求最大流的通用程序吧，因为有的题目里没有当前流量这个东西。
2.还有那个输出f是什么东东？？可行流矩阵式什么意思？？矩阵的含义完全不懂。比如说这个程序运行出来的那个矩阵我就不清楚他的意思。郁闷。

谢谢啦。

zan

编写程序