mst_d.m

清华大学运筹学课件

%MST_d.m
%This program solves the Minimum Spanning Tree Problem by using Dijkstra Algorithm.
n=input('Enter the vertices number of the graph:n= ')
W=input('Enter the weight adjacent matrix of the graph:[W(1,1),..,W(1,n);..;W(n,1),..,W(n,n)]=')

%step0: preparation

S=ones(1,n); S(1)=0; %S is the chosen vertices set, if v(i)has been chosen then S(i)=0.
U=ones(1,n)*inf; %U is the changing weight adjacent matrix currently. 
MST=ones(n)*inf; %MST is the weight adjacent matrix of the Minimum Spanning Tree 
k=1; % choosing vertix k 

%main steps

while any(S)==1 %the stop-condition of the algorithm is S=0. 
   
%step2
   for j=1:n
      if U(j)>=W(k,j)   U(j)=W(k,j);    
      end
   end %U(j)=min{U(j),W(k,j)} for all S(j)>0
%step2 end
   
%step1 
%U(k)=min{U(j)} for all S(j)>0
   min=inf; 
   for j=1:n 
      if S(j)>0
         if U(j)<=min   min=U(j); k=j;   
         end
      end
   end
%U(k)=W(i,k)
   for i=1:n 
      if S(i)==0
         if W(i,k)==min;
            break
         end
      end
   end 
%change the weight matrix of the Minimum Spanning Tree
   MST(i,k)=min;   MST(k,i)=min;
%change the chosen vertices set S=S\{k}
   S(k)=0;
%step1 end

end

%tell if there ia a Minimum Spanning Tree:|E|=|V|-1 ?  
mst=zeros(n);
for i=1:n
   for j=1:n
      if MST(i,j)~=inf   mst(i,j)=MST(i,j);   end
      end
   end
if nnz(mst)==(2*n-2) %|E|=|V|-1
   input('The weight matrix of the Minimum Spanning Tree of the graph is:') 
   MST
else %|E|<|V|-1
   input('The graph doesn"t include a Minimum Spanning Tree.')  
end