dijkstra for large networks

by

 

simple dijkstra function for large networks using spare matrix for non-existing links

dijkstra.m
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 dijkstras algorithm, wich finds the 
% minimal cost path between two nodes. Its 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