f_mf.m

清华大学运筹学课件

function y=f_mf(n,C,V0); %n:verties number; C:capacity matrix(C(i,j)=0); V0:given flow value

f=zeros(n); %feasible flow
Vf=sum(f(1,:)); %feasible flow value          
while Vf<V0
   %construct N(f)
   NC=zeros(n); %the capacity matrix in N(f)
   for i=1:n
      for j=1:n
         if (C(i,j)>0)&(f(i,j)==C(i,j))   NC(j,i)=C(i,j); 
         elseif (C(i,j)>0)&(f(i,j)==0)   NC(i,j)=C(i,j);  
         elseif (C(i,j)>0)&(f(i,j)>0)&(f(i,j)<C(i,j))   NC(j,i)=f(i,j); NC(i,j)=C(i,j)-f(i,j);
         end
      end
   end
   %find generation using Floyd algorithm
   %make nc fit for Floyd algorithm
   nc=NC; 
   for i=1:n
      for j=1:n
         if (NC(i,j)==0)&(i~=j)  nc(i,j)=inf;
         elseif NC(i,j)>0  nc(i,j)=1;
         end
      end
   end %nc(i,i)=0 and nc(i,j)=inf
   for m=1:n
      for i=1:n
         for j=1:n
            if nc(i,j)>nc(i,m)+nc(m,j)  nc(i,j)=nc(i,m)+nc(m,j);  end
         end
      end
   end
   h=nc(1,:); %h(j) is the generation of j
   if h(n)==inf %f:max flow 
      break
   end 
   %construct AN(f)
   ANC=zeros(n);
   for i=1:n
      for j=1:n
         if h(j)==(h(i)+1)  ANC(i,j)=NC(i,j);
         end
      end
   end
   %step2
   cp=inf;
   while cp~=0
      anc=ANC;
      for i=1:n
         for j=1:n
            if (ANC(i,j)==0)&(i~=j)  anc(i,j)=inf;
            elseif ANC(i,j)>0  anc(i,j)=1;
            end
         end
      end
      P=f_short(n,anc); %P:the argument path
      %step3
      pc=ones(1,n)*inf; 
      for i=1:(n-1)
         if P(i+1)~=0   pc(i)=ANC(P(i),P(i+1));   end
      end
      cp=min(pc); 
      if cp>=(V0-Vf)
         for i=1:(n-1)
            if P(i+1)~=0 
               ANC(P(i),P(i+1))=ANC(P(i),P(i+1))-(V0-Vf);
               f(P(i),P(i+1))=f(P(i),P(i+1))+(V0-Vf);  cp=0;
            end
         end
      else
         for i=1:(n-1)
            if P(i+1)~=0 
               ANC(P(i),P(i+1))=ANC(P(i),P(i+1))-cp; f(P(i),P(i+1))=f(P(i),P(i+1))+cp;
            end 
         end
      end
   end
   Vf=sum(f(1,:));           
end

y=f;