1.5

1.5 | 2 ratings Rate this file 31 Downloads (last 30 days) File Size: 59.8 KB File ID: #17385
image thumbnail

dijsktra path finder

by

 

04 Nov 2007 (Updated )

Mex implementation of the dijkstra algorithm

| Watch this File

File Information
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 file inspired 2 D Random Paths Generator Integrating Leg's Contraints.

MATLAB release MATLAB 7.5 (R2007b)
Other requirements A C compiler
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (11)
24 Jan 2014 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

22 Jan 2014 Sebastien PARIS

Pete ...

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

20 Jan 2014 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

04 Mar 2012 Sebastien PARIS

Derek,

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

mex Radjacency.c with -largeArrayDims

Sebastien

02 Mar 2012 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.)

16 Nov 2011 Sebastien PARIS

Roberto,

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

16 Nov 2011 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...

16 Nov 2011 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

04 Apr 2008 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.

03 Apr 2008 Johnathan Abelsford

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

02 Apr 2008 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
01 Mar 2009

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

17 Nov 2011

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

27 Jan 2014

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

Contact us