mf.m

清华大学运筹学课件

%MF.m
%This program  solves the maximum flow problem by using Dinic algorithm.

n=input('Enter the vertices number of the graph:n= ')
C=input('Enter the capacity adjacent matrix of the graph:[C(1,1),..,C(1,n);..;C(n,1),..,C(n,n)]=') 
%C(i,j)=0 if (i,j) isn't in graph

%stpe0: preparation

f=zeros(n); %f is a feasible flow

%main steps

for time=1:n %step2.5

%step1
   %construct N(f)
   NC=zeros(n); %NC is 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 %fis the maximum 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
%step1 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 is the argument path
%step2 end

%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);
  
      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
%step3 end
   
end

input('the maximum flow is:')
f
input ('the maximun flow value is')
Vf=sum(f(1,:))