最短路dijkstra算法Matlab程序.doc

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