dijkstras.m

这是一个求最短路的算法

function [path,dist]=DIJKSTRAs(W,S,T)
% Find shortest path from point S to piont T for positive weight matrix W
% by Dijkstra method. This is the fastest routine.
% Input   - W is the positive weight, of which the diagonal may be either 0
%           or inf.
%         - S starting point,
%         - T terminal point
% Output  - path is the shortest path from S to T
%         - dist is the shortest distance.
n=length(W); % number of points
P=zeros(4,n); % P(3,j) will at last put the shortest distance from point S to point j. P(2,j) will be the point where the poimt j is come from
P(1,:)=1:n; % P(1,:) is the indexes of the points
pt=S; 
P(3,:)=W(S,:);
P(4,find(P(3,:)~=inf))=2; % here P(4,:) is used as an temperary variable
Plabel=[];
for k=1:n-1
    Plabel=[Plabel,pt]; % the permanent points
    Ptemp=P([1,3],:);
    Ptemp(:,Plabel)=[]; % denote P-label by inf
    P(2,find(P(4,:)==2))=pt; % the point is come from pt
    W(:,pt)=inf; % delete the edges linking to pt
    [miniw, P(2,S)]=min(Ptemp(2,:)); 
    pt=Ptemp(1,P(2,S));% point pt is the new P-label point
    if pt==T break; end
    [P(3,:),P(4,:)]=min([P(3,:);miniw+W(pt,:)]);
end
P(4,:)=[zeros(1,n-1),T]; % Hereafter  P(4,:) is used to storage the points on the path 
for k=n:-1:2 % find the path from point S to point T
   P(4,k-1)=P(2,P(4,k));
   if P(4,k-1)==S , path=P(4,(k-1):n); dist=P(3,T); return; end
end