dijsktra path finder

Mex implementation of the dijkstra algorithm

Description

Return the optimal path given the adjacency/cost sparse matrix and source/destination nodes.

Run mexme_dijkstra.m to compile mex-files on your own-plateform.
Be sure that "mex -setup" have been done at least one.

Run test_dijkstra.m for the demo

• Acknowledgements: This submission has inspired the following:; 2D random paths generator integrating leg's contraints
• MATLAB release: MATLAB 7.5 (R2007b)
• Other requirements: A C compiler

[ANDREW KOH]

Invalid MEX-file 'C:\JOBS\MATLAB\MATLABCCA\JointPaper\dijkstra.dll': The specified procedure could not be found.

I am using WIN32 MATLAB RELEASE 7

[Johnathan Abelsford]

There is no documentation or help to explain to novice users how to use the program.

[Sébastien Paris]

All helps are included in each C mex-files with examples. Please recompile theses mex-files if you are working with older plateforms.

[Roberto Olmi]

Useful tool, thanks.
However a with this code (see below) the the function dinds correcly only the cost of the path but not the path.
Any suggestions?
Thanks

Roberto Olmi

I=[2,11,1,3,2,17,19,26,4,5,6,...
7,8,9,1,10,11,12,13,14,20,15,...
22,3,18,17,4,16,23,15,21,20,...
16,24,19,25,22,23,4];
J=[1,1,2,2,3,3,4,4,5,6,7,8,9,...
   10,11,11,12,13,14,15,15,...
   16,16,17,17,18,19,19,19,20,...
   20,21,22,22,23,23,24,25,26];
V=[1.6000,6.0000,2.6667,1.6000,...
   2.6667,1.2000,7.2240,4.2000,...
   3.6000,3.2000,3.2000,2.6000,...
   2.8000,2.6000,3.6000,7.2240,...
   2.4000,3.2000,2.6000,3.0000,...
   2.9120,2.0000,2.7120,2.0000,...
   1.2000,2.0000,7.2240,4.8000,...
   2.7120,4.8533,0.4000,0.6667,...
   4.5200,0.4000,4.5200,0.4000,...
   0.6667,0.6667,7.0000];
pcost=sparse(I,J,V,length(I),length(I));

pcost(2,1) %check edge 1
pcost(1,11) %check edge 2
pcost(11,12) %check edge 3
[path cost]=dijkstra(pcost,2,12) %search the path 2-1-11-12
%the cost is found correctly but not the path

[Roberto Olmi]

Hi Sébastien,
I think that in order to fix this bug you have to initialize parent[i] to -1:
for (i = 0 ; i < n ; i++)
{ distance[i] = inf;
   parent[i] = -1; //instead of = 0
   visited[i] = 0;
}
and then modify the check you do before backtracking to:
if(parent[s] != -1) //instead of != 0
{...

I've tested it and solves at least my problem...

Regards.

Roberto Olmi

PS: In the code you use the "s" variable to represent the destination node and the "d" to represent the source. This is slightly confusing...

[Sebastien Paris]

Roberto,

Thank your for reporting. I will update with your modification.
Sébastien