sp_f.m

清华大学运筹学课件

%SP_f.m
%This program solves the Shortest Path Problem by using Floyd 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

U=W; %U is the weight adjacent matrix of the Shortest Path
S=zeros(n,n); %S is the labelling matrix of the Shortest Path
   for i=1:n
      for j=1:n   S(i,j)=j;  
      end
   end  
   
%main steps:step1  
for m=1:n
   for i=1:n
      for j=1:n
         if U(i,j)>U(i,m)+U(m,j)  S(i,j)=S(i,m); U(i,j)=U(i,m)+U(m,j);  
         end
      end
   end
end
%step1 end

input('the weight adjacent matrix of the Shortest Path between each pair of vertices is:')
U
input('the leballing matrix of the Shortest Path between each pair of vertices is:')
S