求网络最大流及最小费用最大流问题的 Ford-Fulkerson标

求网络最大流及最小费用最大流问题的 Ford-Fulkerson标 最优化方法上机实验3 求网络最大流及最小费用最大流问题的 Ford-Fulkerson标号算法 上机时间:2014.01.07 1例 求下图所示网络的最大流 (5,2)Vv41 (4,2)(3,3)(5,5) (3,3)(3,0)(4,2)vv5tv2vs (2,2)(3,2)(5,4) vv36(2,2) 2例求下图所示网络的最小费用最大流，弧旁(,)bc中的bc,分别示顶点iijijijij 到顶点j间弧的费用和容量。 v2 (3,5) (10.12) v3实验 (6,7)(4,7)vtvs 问题 (5,9)(3,8)(12,10) 描述 (5,8)v4 (2,7) v5 b=[0 10 6 3 0 0; 0 0 4 0 0 3; 0 0 0 0 12 4; 0 0 5 0 2 0; 0 0 0 0 0 5; 0 0 0 0 0 0]; c=[0 12 7 8 0 0; 0 0 8 0 0 5; 0 0 0 0 10 7; 0 0 9 0 7 0; 0 0 0 0 0 8; 0 0 0 0 0 0]; [f wf zwf]=BGf(c,b) 1. 算法原理 Ford-Fulkerson算法是一种迭代算法，首先对图中所有顶点对的流大小清零，此时的网络流大小也为0。在每次迭代中，通过寻找一条“增广路径”(augument path)来增加流的值。增广路径可以看作是源点s到汇点t的一条路径，并且沿着这条路径可以增加更多的流。迭代直至无法再找到增广路径位置，此时必然从源点到汇点的所有路径中都至少有一条边的满边(即边的流的大小等于边的容量大小)。 2.算法: STEP0 置初始可行流x(如零流);对节点t标号，即令maxf(t)=任意正值。 STEP1 若maxf(t) > 0，继续下一步;否则停止，已经得到最大流，结束。 原理 STEP2 取消所有节点 j?V 的标号，即令maxf(j) = 0， pred(j) = 0;令 及 LIST={ s }，对节点s标号，即令maxf(s) =充分大的正值。 算法 STEP3 如果 LIST? Φ且maxf(t) = 0，继续下一步;否则: (3a)如果t已经有标号(即maxf(t) > 0)，则找到了一条增广路，沿该增广路对流x进行增广(增广的流量为maxf(t)，增广路可以根据 pred 回溯方便地得到)，转 STEP1。 (3b)如果t没有标号(即 LIST=Φ且maxf(t) = 0)，则停止，已得到最大流。 STEP4 从 LIST 中移走一个节点i;寻找从节点i出发的所有可能的增广弧: (4a)对非饱和前向弧(i, j)，若节点 j没有标号(即pred(j) = 0)，对 j 进行标号，并将 j加入 LIST 中。 (4b)对非空后向弧(j,i)，若节点 j没有标号(即pred(j) = 0)，对 j进行标号，并将 j 加入 LIST 中。 完 3.1Ford-Fulkerson标号算法 clc,clear u=[0 5 4 3 0 0 0 0; 整 0 0 0 0 5 3 0 0; 0 0 0 0 0 3 2 0; 程 0 0 0 0 0 0 2 0; 序 0 0 0 0 0 0 0 4; 0 0 0 0 0 0 0 3; 0 0 0 0 0 0 0 5; 清 0 0 0 0 0 0 0 0]; 单 n=length(u); f=zeros(n,n); list=[];maxf(n)=1; , while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); 含 list=1;record=list;maxf(1)=inf; %list是未检查邻接点的标号点，record是已标号点 注 while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; 释 label1= find(u(flag,:)-f(flag,:)); , label1=setdiff(label1,record); list=union(list,label1); pred(label1)=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2)=-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 3.2最小费用最大流问题程序: function[f wf zwf]=BGf(C,b) %C表示弧容量矩阵 %b表示弧上单位流量的费用 %f表示最小费用最大流矩阵 %wf表示最大流量 %zwf表示最小费用 n=size(C,2); wf=0;wf0=Inf; %wf表示最大流量，wf0表示预定的流量值 f=zeros(n,n); %取初始可行流f为零流 while(1) a=ones(n,n)*inf; for(i=1:n) a(i,i)=0; end %构造有向赋权图a for(i=1:n) for(j=1:n) if(C(i,j)>0&f(i,j)==0) a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j)) a(j,i)=-b(i,j); elseif(C(i,j)>0) a(i,j)=b(i,j); a(j,i)=b(i,j); end end end for(i=2:n) p(i)=Inf;s(i)=i; end %用Floyd算法求最短路，赋初值 for(k=1:n) pd=1; %求有向赋权图中vs到vt的最短路 for(i=2:n) for(j=1:n) if(p(i)>p(j)+a(j,i)) p(i)=p(j)+a(j,i);s(i)=j;pd=0; end end end if(pd) break; end end %求最短路的Floyd算法结束 if(p(n)==Inf) break; end %不存在vs到vt的最短路，算法终止 %注意在求最小费用最大流时构造有向赋权图中不会含 %负权回路，所以不会出现k=n dvt=Inf;t=n; %进入调整过程，dvt表示调整量 while(1) if(a(s(t),t)>0) dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0) dvtt=f(t,s(t)); end %后向弧调整量 if(dvt>dvtt) dvt=dvtt; end if(s(t)==1) break; end %当t的标号为vs时，终止计算调整量 t=s(t); end %继续调整前一段弧上的流f pd=0; if(wf+dvt>=wf0) dvt=wf0-wf;pd=1; end %如果最大流量大于或等于预定的流量值 t=n; while(1) %调整过程 if(a(s(t),t)>0) f(s(t),t)=f(s(t),t)+dvt; %前向弧调整 elseif(a(s(t),t)<0) f(t,s(t))=f(t,s(t))-dvt; end %后向弧调整 if(s(t)==1) break; end %当t的标号为vs时，终止调整过程 t=s(t); end if(pd) break; end %如果最大流量达到预定的流量值 wf=0; for(j=1:n) wf=wf+f(1,j); end end %计算最大流量 zwf=0; for(i=1:n) for(j=1:n) zwf=zwf+b(i,j)*f(i,j); end end end %计算最小费用 f; %最小费用最大流 %%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%% 实验结果: 实 例4.17 解 >> b=[1 1 1 1 1 1 2 2 2 3 3 4 4 4 5 5;2 3 4 5 6 7 3 5 7 4 7 5 6 7 6 7;1 8 5 3 7 4 6 10 7 2 9 4 5 6 9 验 10]; >> C=[0 5 4 3 0 0 0 0; 结 0 0 0 0 5 3 0 0; 0 0 0 0 0 3 2 0; 果 0 0 0 0 0 0 2 0; ,结果式、 0 0 0 0 0 0 0 4; 数据表、 0 0 0 0 0 0 0 3; 图形, 0 0 0 0 0 0 0 5; 0 0 0 0 0 0 0 0]; [q w e]=fofuf(C) 例4.18 解: >> a=[1 1 1 2 2 3 3 4;2 3 4 3 5 4 5 5;5 3 7 8 4 1 6 2]; >> [T,c]=Krusf(a,1) T = 3 4 1 2 4 5 3 5 c = 10 >> a=[0 5 3 7 inf;5 0 8 inf 4;3 8 0 1 6;7 inf 1 0 2;inf 4 6 2 0]; >> [T c] =Primf(a) T = 1 3 4 5 3 4 5 2 c = 10 从两种方法得到的最小生成树不同，但权和都为10. 实 在最优化上机实验中，将数学语言转化成了计算机语言，通过学习 Ford-Fulkerson算法，我掌握了更加高效的解决最大流和最小费用最大流问题。验 通过学习编程代码，我学习了最大流的算法，同一个连通图的最大流是唯一的。 通过学习，提高了编程水平。 体 会 实验日期: 2014年1月7日