zhuliu1.m

清华大学运筹学课件

input(' This program  solves the minimum-cost flow problem.')
n=input('Enter the number of the verties : ')
W=input('Enter the cost matrix as W(n,n):   ') %W(i,j)=inf if (i,j) isn't in graph
r=input('Enter the root vertix:   ')
%step0
Wm=W;  Vm=n; no=0;%if goto step4
C=zeros(2*n);

for m=1:n
   %step1 
   %find min-arc set Hm
   Hm=zeros(n); 
   for j=1:n
      if j~=r
         min=min(W(:,j));
         for i=1:n
            if W(i,j)==min   Hm(i,j)=Wm(i,j);  break
            end
         end
      end
   end

   if nnz(Hm)<Vm-1  no=1;%not goto step4
        break
   end
    
   %step 2
   %find direct cycle in Hm
   for i=1:n
      for j=1:n
         if Hm(i,j)~=0  Hm(i,j)=-1;
         elseif (i~=j)&(Hm(i,j)==0)  Hm(i,j)=inf;
         end
      end
   end
   Cm=f_cycle(n,Hm); 
   if Cm==zeros(1,n+1)  %no cycle,go to step4 
      break   
   end
   
   %step 3
   C(m,1:(n+1))=Cm; %cycle matrix
   MIN=zeros(n); %min-value matrix
   Vm=Vm-nnz(Cm)+1; %vertix number
   Wm(n+1:n+1,1:n)=ones(1,n)*inf;  Wm(1:n+1,n+1:n+1)=ones(n+1,1)*inf; %expand Wm to (n+1,n+1)
   mW=Wm;
   for j=1:n
      for i=1:n
         for k=2:(n+1)
            if j==Cm(k)  mW(i,j)=Wm(i,j)-Wm(Cm(k-1),Cm(k)); end
         end
      end
   end
   for i=1:(n+1)
      for k=1:n
         if i==Cm(k)  mW(i,n+1)=min(mW(i,n+1),mW(i,j));  mW(i,:)=ones(1,n+1)*inf;
                      mW(n+1,i)=min(mW(n+1,i),mW(j,i));  mW(:,i)=ones(n+1,1)*inf;
         end
      end
   end
   Wm=mW;
   for i=1:n
      for j=1:n
         if mW(i,j)==mW(i,n+1) MIN(i,j)=m;  
         elseif mW(j,i)==mW(n+i,i) MIN(j,i)=m; 
            
      
                

             
               
               
               
               
                                             
               
               
                  
               
                  
                  
     
      
            n=n+1;
    
      
      
      
           
   end
end

%step4
if no==1 %from step1
   input('there isn"t a spanning tree rooting r')
else %from step2
   while m~=1
      
      
      
      
      
      
      
      
      
      m=m-1;end
end

input('the mim-spanning tree is:')
Hm