sp_d.m

清华大学运筹学课件

%SP_d.m
%This program solves the Shortest Path 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

T=1:n; T(1)=0; %T is the chosen vertices set, if v(i) has been chosen then T(i)=0.
P=zeros(1,n); %P is the pre-vertix labelling set.
i=1; %the orginal labelling: P(j)=1
U=ones(1,n)*inf; U(1)=0; %U is the changing weight adjacent matrix currently. 

%main steps

for r=1:n %the stop-condition of the algorithm is S=0. 
   
%step3 
   for j=1:n 
      if U(j)>W(i,j)+U(i)
         U(j)=W(i,j)+U(i);  P(j)=i;
      end
   end %U(j)=min{U(j),W(k,j)}  
%step3 end
   
%step1 
   min=inf;
   for j=1:n
      if (T(j)>0)&(U(j)<=min)    min=U(j); i=j;   
      end 
   end %U(i)=min{U(j)}  
%step1 end
   
   
%step2
  T(i)=0; % choose v(i)
%step2 end

end 

input('the pre-vertix labelling of the shortest path (from 1 to the other) is:') 
P