varargout=shortest_path_dijkstra(varargin)

function varargout=shortest_path_dijkstra(varargin)
%SHORTEST_PATH_DIJKSTRA Compute shortest path between two edges in a
%directed/undirected graph with wages.
%   PATH=SHORTEST_PATH_DIJKSTRA(BEGIN,END,NAME,STRUC_DIM) uses Dijkstra's
%   algorithm [1] for computing shortest path between BEGIN and END node
%   for a NAME.mat network (ie. help CREATE_NETWORK). STRUC_DIM is the
%   structure number saved in NAME.mat file.
%
%   See also CREATE_NETWORK, CREATE_RAND_NETWORK, SHORTEST_PATH_BFS.
%
%   References:
%      [1]  T. E. Cormen et al., "Introduction to Algorithms", 
%      WNT, Warsaw 2000, page 593.

%   Copyright 2003-2004 Przemyslaw Pawelczak
%   E-mail: [e-mail]
%   Wroclaw University of Technology, Poland
%   $Revision: 1.0 $  $Date: 2004/01/31 16:28:13 $

%If no NUMBER specified then it will be first
if nargin==3
    varargin{4}=1;
end

%Exeption handling
message=nargchk(3,4,nargin);
testing_int=[varargin{1},varargin{2},varargin{4}];
if ~isempty(message)
    error('MATLAB:SHORTEST_PATH_DIJKSTRA:NumberOfInputArguments',...
        message);
end 
if find(isnan(testing_int))
    error('MATLAB:SHORTEST_PATH_DIJKSTRA:ArgumentType',...
        'Arguments must be numbers.');
end
%Check if VARARGIN are positive integers
if sum([testing_int<0,fix(testing_int)~=testing_int])~=0
    error('MATLAB:SHORTEST_PATH_DIJKSTRA:ArgumentType',...
        'Arguments must be positive integers.');
end
if ~isstr(varargin{3})
    error('MATLAB:SHORTEST_PATH_DIJKSTRA:ArgumentType',...
        'Argument must be string.');
end

%Change string into number (for all number arguments)
for k=[1,2,4]
    if isstr(varargin{k})==1
        varargin{k}=str2num(varargin{k});
    end
end

%List all '*.mat' files in current working directory
%Change directory to MATLABROOT\networks - catalog must exist
cd([matlabroot,['\work\networks']]);
directory=what;
directory=struct2cell(directory);
directory=cellstr(directory{3});

%Check if specified '*.mat' file already exist
if find(strcmp(directory,[varargin{3},'.mat'])==1)
    load(varargin{3});
    fields_vector=[exist('description'),exist('structure')];
    if length(find(fields_vector))~=2
        error('MATLAB:SHORTEST_PATH_DIJKSTRA:BadFieldNames',...
            'Bad field names.'); 
    else
        varargout{1}=dijkstra(varargin{1},varargin{2},structure,varargin{4});
    end
else
    error('MATLAB:SHORTEST_PATH_DIJKSTRA:BadFileName',...
        'Bad file name.'); 
end

function [road]=dijkstra(begin_node,end_node,structure,number)

%Check how many nodes are in the graph
structure_dimension=cellfun('ndims',structure);
structure_length=length(structure_dimension(:,1,1));
node_number=0;
for k=1:structure_length
    if ~isempty(structure{k,1,number})
        node_number=node_number+1;
    end
end

%Dijkstra's algorithm (taken form [1])

%Initialize single source
distance(1:node_number)=Inf;
previous(1:node_number)=NaN;
distance(begin_node)=0;
%Initialize queue and minimum wages scalar S
S=[];
queue(1:node_number)=1:node_number;

while length(S)~=node_number
    %Extract min
    places=find(queue==Inf);
    distance_temp=distance;
    distance_temp(places)=NaN;
    %function MIN chooses all min elements in vector
    position=find(distance_temp==min(distance_temp));
    %Assign smallest element to u
    u=queue(position(1));
    %Add new element to S
    S=[S,u];
    %Remove from queue (replace it by Inf)
    queue(position(1))=Inf;
    node_incidence_vector=structure{u,1,number};
    for k=1:length(node_incidence_vector)
        %Relaxation
        if distance(node_incidence_vector(k))>distance(u)+structure{u,2,number}(k)
            distance(node_incidence_vector(k))=distance(u)+structure{u,2,number}(k);
            previous(node_incidence_vector(k))=u;
        end
    end
end

%Show path
road=[];
position=end_node;
while position~=begin_node
    road=[road,previous(position)];
    position=previous(position);
end

road=fliplr([end_node,road]);