function D = dijkstra( G , S )
% --------------------------------------------------------------------
%      Mark Steyvers, Stanford University, 12/19/00
% --------------------------------------------------------------------
%
% DIJKSTRA  Find shortest paths in graphs
% 	D = dijkstra( G , S ) use the full or sparse matrix G in which 
% 	an entry (i,j) represents the arc length between nodes i and j in a 
%	graph. In a full matrix, the value INF represents the absence of an arc; 
%	in a sparse matrix, no entry at (i,j) naturally represents no arc.
%		
%	S is the one-dimensional matrix of source nodes for which the shortest
%	to ALL other nodes in the graphs will be calculated. The output matrices
%	D and P contain the shortest distances and predecessor indices respectively.
%	An infinite distance is represented by INF. The predecessor indices contain
%	the node indices of the node along the shortest path before the destination
%	is reached. These indices are useful to construct the shortest path with the
%	function pred2path (by Michael G. Kay).
%
%	This function was implemented in C++. The source code can be compiled to a
%	Matlab compatible mex file by the command "mex -O dijkstra.cpp" at the Matlab
%	prompt. In this package, we provide a compiled .dll version that is 
%       compatible all Windows based machines.  If you are not working on a 
%       Windows platform, delete the .dll version provided and recompile from
%       the .cpp source file.  If you do not have the Matlab compiler or a Windows
%       platform, delete the .dll version and dijkstra will then call the
%	Matlab function dijk.m (by Michael G. Kay).  Note that this Matlab
%	code is several orders of magnitude slower than the C based mex file.

N = size( G , 1 );
D = dijk( G , S , 1:N );