File Exchange

image thumbnail

dijsktra path finder

version 1.4.0.0 (57.4 KB) by Sebastien PARIS
Mex implementation of the dijkstra algorithm

4 Downloads

Updated 28 Jan 2020

View Version History

View License

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

Cite As

Sebastien PARIS (2021). dijsktra path finder (https://www.mathworks.com/matlabcentral/fileexchange/17385-dijsktra-path-finder), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (12)

nuts qiang

Pete

Sebastien,

It seems as though I just needed to add the " -largeArrayDims" option to all of the mex files in mexme_dijkstra.m. Sorry for not catching this sooner.

-Pete

Sebastien PARIS

Pete ...

What is your version of Matlab, compiler you are using ? and CPU ?

Pete

Sebastien,

I tried to implement your suggestion the Derek's problem by adding that option in the mexme_dijkstra file. However, I still get the same error that he was getting. This was the exact line of code that I placed into that file on line 5:

mex Radjacency.c -largeArrayDims

The error that I'm getting is:

"??? Error using ==> dijkstra
Function "mxGetJc_700" is obsolete.
(64-bit mex files using sparse matrices must be rebuilt with
the "-largeArrayDims" option. See the R2006b release notes
for more details.)

Error in ==> test_dijkstra at 39
[path , pathcost] = dijkstra(A , s , d);"

I would really like to utilize your algorithm implementation. Any help that you could provide is greatly appreciated!

Best Wishes,

Pete

Sebastien PARIS

Derek,

Try to recompile Radjacency.c with -largeArrayDims option such:

mex Radjacency.c with -largeArrayDims

Sebastien

Derek O'Connor

Error using Radjacency
Function "mxGetIr_700" is obsolete.
(64-bit mex files using sparse matrices must be rebuilt with the "-largeArrayDims" option. See the
R2006b release notes for more details.)

Sebastien PARIS

Roberto,

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

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...

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

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.

Johnathan Abelsford

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

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

MATLAB Release Compatibility
Created with R2016b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!