function [c0,c,path0,path]=dijkstra(s,t,C,flag)
% Use the Dijkstra's algorithm to find the shortest path from
% s to t and can also find the shortest path between s and all
% the other points.
% Reference: Graph Theory with Applications by J. A. Bondy and
% U. S. R. Murty.
% Input -- s is the starting point and also is the point s.
% -- t is the given terminal point and is the point t.
% -- C \in R^{n \times n}is the cost matrix, where
% C(i,j)>=0 is the cost from point i to point j.
% If there is no direct connection between point i and
% j, C(i,j)=inf.
% -- flag: if flag=1, the function just reports the
% shortest path between s and t; if flag~=1, the
% function reports the shortest path between s and t,
% and the shortest paths between s and other points.
% Output -- c0 is the minimal cost from s to t.
% -- path0 denotes the shortest path form s to t.
% -- c \in R{1\times n} in which the element i is the
% minimal cost from s to point i.
% -- path \in R^{n \times n} in which the row i denotes
% the shortest path from s to point i.
% Copyright by MingHua Xu(徐明华), Changhzou University, 27 Jan. 2014. s=floor(s);
t=floor(t);
n=size(C,1);
if s<1 || t < 1 || s > n || t > n
error(' The starting point and the terminal point exceeds the valid range');
end
if t==s
disp('The starting point and the terminal point are the same points');
end
label=ones(1,n)*inf;
label(s)=0;
S=[s];
Sbar=[1:s-1,s+1:n];
c0=0;
path=zeros(n,n);
path(:,1)=s;
c=ones(1,n)*inf;
parent=zeros(1,n);
i=1; % number of points in point set S.
while i<n
% for each point in Sbar, replace label(Sbar(j)) by
% min(label(Sbar(j)),label(S(k))+C(S(k),Sbar(j)))
for j=1:n-i
for k=1:i
if label(Sbar(j)) > label(S(k))+C(S(k),Sbar(j))
label(Sbar(j))=label(S(k))+C(S(k),Sbar(j));
parent(Sbar(j))=S(k);
end
end
end
% Find the minmal label(j), j \in Sbar.
temp=label(Sbar(1));
son=1;
for j=2:n-i
if label(Sbar(j))< temp
temp=label(Sbar(j));
son=j;
end
end
% update the point set S and Sbar
S=[S,Sbar(son)];
Sbar=[Sbar(1:son-1),Sbar(son+1:n-i)];
i=i+1;
% if flag==1, just output the shortest path between s and t.
if flag==1 && S(i)==t
son=t;
temp_path=[son];
if son~=s
while parent(son)~=s
son=parent(son);
temp_path=[temp_path,son];
end
temp_path=[temp_path,s];
end
temp_path=fliplr(temp_path);
m=size(temp_path,2);
path0(1:m)=temp_path;
c_temp=0;
for j=1:m-1
c_temp=c_temp+C(temp_path(j),temp_path(j+1));
end
c0=c_temp;
path(t,1:m)=path0;
c(t)=c0;
return
end
end
% Form the output results
for i=1:n
son=i;
temp_path=[son];
if son~=s
while parent(son)~=s
son=parent(son);
temp_path=[temp_path,son];
end
temp_path=[temp_path,s];
end
temp_path=fliplr(temp_path);
m=size(temp_path,2);
path(i,1:m)=temp_path;
c_temp=0;
for j=1:m-1
c_temp=c_temp+C(temp_path(j),temp_path(j+1));
end
c(i)=c_temp;
c0=c(t);
path0=path(t,:);
end
return。