I think you could speed up Dirk Stelder's solution by replacing the first for loop (between "candidate=[];' and "[u_index u]=min(candidate);") by the statement
[u_index u] = min(1 ./ (S==0) .* dist);
(Note that u_index is in fact the value; u is the index.) Entries in 1 ./ (S==0) have value Inf when their value in S is 1, i.e. when they have been visited, and 1 otherwise. Multiplying by dist leaves all visited nodes with distance Inf: precisely what 'candidate' looks like.
here is a simple rewrite that runs well for large networks. Th costmatrix is sparse (no entries for non-existing links) and only total costs are calculated:
function [spcost] = dijkstra(costmatrix, s, d)
% uses sparse matrix and ingores paths to save time and memory for large networks
% calculates totals cost only
% This is an implementation of the dijkstra´s algorithm, wich finds the
% minimal cost path between two nodes. It´s supoussed to solve the problem on
% possitive weighted instances.
% inputs:
% n*n costmatrix, can be sparse for nonexisting links
% n: the number of nodes in the network;
% s: source node index;
% d: destination node index;
%For information about this algorithm visit:
%http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
%This implementatios is inspired by the Xiaodong Wang's implememtation of
%the dijkstra's algorithm, available at
%http://www.mathworks.com/matlabcentral/fileexchange
%file ID 5550
%Author: Jorge Ignacio Barrera Alviar. April/2007
%Edited Dirk Stelder September/2013
n=size(costmatrix,1);
S(1:n) = 0; % vector, set of visited vectors
dist(1:n) = inf; % it stores the shortest distance between the source node and any other node;
prev(1:n) = n+1; % Previous node, informs about the best previous node known to reach each network node
dist(s) = 0;
while sum(S)~=n
candidate=[];
for i=1:n
if S(i)==0
candidate=[candidate dist(i)];
else
candidate=[candidate inf];
end
end
[u_index u]=min(candidate);
S(u)=1;
for i=1:n
if costmatrix(u,i)>0 % ignore non-existing links (=zero in sparse matrices) to save time and memory
if(dist(u)+costmatrix(u,i))<dist(i)
dist(i)=dist(u)+costmatrix(u,i);
prev(i)=u;
end
end
end
end
spcost = dist(d);
This is great code. As others have pointed out, it could be commented better, but having said that, it's the easiest implementation of Dijkstra's Algorithm to understand that is available on the file exchange. As a beginner programmer, I appreciate the simplicity.
The previous commenter pointed out, matriz-costo is an n x n adjacency matrix. To elaborate, elements reflect the cost of traveling between corresponding nodes. Any element set to zero implies a cost-free path exists between those two nodes. I usually set the elements corresponding to non-adjacent nodes to an arbitrarily large number (it might also work to set them to inf -- I haven't tried it).
My one wish is that the output included multiple paths if there is a tie for which path is shortest. I modified the code to return ties. It is posted here:
http://www.mathworks.com/matlabcentral/fileexchange/36086
Thank you!!
Comment only