Rank: 7850 based on 8 downloads (last 30 days) and 1 file submitted
photo

Dirk Stelder

E-mail

Personal Profile:

 

Watch this Author's files

 

Files Posted by Dirk Stelder
Updated   File Tags Downloads
(last 30 days)
Comments Rating
12 Sep 2013 dijkstra for large networks simple dijkstra function for large networks using spare matrix for non-existing links Author: Dirk Stelder dijkstra, shortest path 8 0
Comments and Ratings by Dirk Stelder
Updated File Comments Rating
12 Sep 2013 dijkstra very simple Dijkstra's algorithm to find the shortest path Author: Jorge Barrera

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);

Contact us