File Exchange

image thumbnail

dijsktra path finder

version 1.3 (59.8 KB) by

Mex implementation of the dijkstra algorithm

2.66667
3 Ratings

9 Downloads

Updated

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

Comments and Ratings (12)

nuts qiang

Pete

Pete (view profile)

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

Pete (view profile)

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

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

Updates

1.3

- Changed int* to mwIndex* for OS64. Now should work also for 64bits system

1.2

-Fix a bug thanks Roberto Olmi for reporting
- Cosmetic changes
- Should be work with Linux/GCC system

1.1

-add test_dijkstra.m and mexme_dijkstra.m
-improved qsindex algorithm

MATLAB Release
MATLAB 7.5 (R2007b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video