varargout=shortest_path_dijkstra_all(varargin)

function varargout=shortest_path_dijkstra_all(varargin)
%SHORTEST_PATH_DIJKSTRA_ALL Compute all shortest paths between two edges in
%a directed/undirected graph with wages.
%   PATH=SHORTEST_PATH_DIJKSTRA_ALL(BEGIN,END,NAME,STRUC_DIM) uses modified
%   Dijkstra's algorithm [1] for computing all shortest paths 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.
%
%   Because it is possible, that graph has more than one path between two
%   nodes with the shortest length this function computes all such paths.
%
%   Dijkstra's algorithm computes only one shortest path choosen randomly
%   among all possible paths (depending how the incidence nodes were
%   given). In this function Dijkstra's algorithm has been modified to
%   manage the task. For details - in MATLAB print EDIT
%   SHORTEST_PATH_DIJKSTRA_ALL. 
%
%   See also SHORTEST_PATH_DIJKSTRA, SHORTEST_PATH_BFS,
%   CREATE_NETWORK, CREATE_RAND_NETWORK.
%
%   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/02/12 17:49:21 $

%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_ALL:NumberOfInputArguments',...
        message);
end 
if find(isnan(testing_int))
    error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL: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_ALL:ArgumentType',...
        'Arguments must be positive integers.');
end
if ~isstr(varargin{3})
    error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL: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_ALL:BadFieldNames',...
            'Bad field names.'); 
    else
        varargout{1}=dijkstra_all(varargin{1},varargin{2},structure,varargin{4});
    end
else
    error('MATLAB:SHORTEST_PATH_DIJKSTRA_ALL:BadFileName',...
        'Bad file name.'); 
end

function [road]=dijkstra_all(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

%Modified Dijkstra's algorithm

%Initialize variables
distance(1:node_number)=Inf;
previous=zeros(1,node_number);
queue(1:node_number)=1:node_number;
S=[];

distance(begin_node)=0;
checker(begin_node)=0;

%Because in this modification distances and previos nodes vectors might be
%different for every end node, they must be initialized separately
for k=1:node_number
    Distance{1,k}=distance;
    Previous{1,k}=previous;
end

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 NODE
    node=queue(position(1));
    %Add new element to S - vector of computed nodes
    S=[S,node];
    %Remove from queue (replace it by Inf)
    queue(position(1))=inf;
    
    node_incidence_vector=structure{node,1,number};
    wages_vector=structure{node,2,number};
    
    for k=1:length(node_incidence_vector)
        road_numbers=struct_size(Distance,node);
        for r=1:road_numbers
            current_distance=Distance{r,node};
            current_previous=Previous{r,node};
            %Relaxation
            if distance(node_incidence_vector(k))>current_distance(node)+wages_vector(k)
                distance(node_incidence_vector(k))=current_distance(node)+wages_vector(k);
                previous(node_incidence_vector(k))=node;
                %If there are distances shorter than previous ones - update
                Distance{1,node_incidence_vector(k)}=distance;
                Previous{1,node_incidence_vector(k)}=previous;
                %And remove all the other distances
                for m=2:size(Previous,1) 
                %SIZE function is used against STRUCT_SIZE because now we
                %can add as many empty vectors as long is the structure,
                %not just as long is the stucture on
                %node_incidence_vector(k) position
                    Distance{m,node_incidence_vector(k)}=[];
                    Previous{m,node_incidence_vector(k)}=[];
                end
            elseif distance(node_incidence_vector(k))==current_distance(node)+wages_vector(k)
                %Update PREVIOUS vector
                current_previous(node_incidence_vector(k))=node;
                %Count how many vectors are in the struct
                road_numbers=struct_size(Distance,node_incidence_vector(k));
                %Update them
                Distance{road_numbers+1,node_incidence_vector(k)}=distance;
                Previous{road_numbers+1,node_incidence_vector(k)}=current_previous;
            end
        end
    end
end

%Show all paths
road_temp=[];
for k=1:struct_size(Previous,end_node)
    road=[];
    position=end_node;
    previous=Previous{k,end_node};
    while position~=begin_node
        road=[road,previous(position)];
        position=previous(position);
    end
    %Store all paths in a matrix
    road_temp=[road_temp;fliplr([end_node,road])];
end
road=road_temp;

function [road_numbers]=struct_size(name,position)
%Check how many dimensions are in the NAME structure
all_dimensions=cellfun('size',name,1);
%Check how long is the structure NAME on POSITION
road_numbers=length(find(all_dimensions(:,position)'));