Code covered by the BSD License  

Highlights from
Advanced Dijkstra's Minimum Path Algorithm

4.9

4.9 | 10 ratings Rate this file 113 Downloads (last 30 days) File Size: 3.92 KB File ID: #20025
image thumbnail

Advanced Dijkstra's Minimum Path Algorithm

by

 

22 May 2008 (Updated )

calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm

| Watch this File

File Information
Description

DIJKSTRA Calculate Minimum Costs and Paths using Dijkstra's Algorithm

Inputs:
[AorV] Either A or V where
 A is a NxN adjacency matrix, where A(I,J) is nonzero if and only if an edge connects point I to point J
 NOTE: Works for both symmetric and asymmetric A
 V is a Nx2 (or Nx3) matrix of x,y,(z) coordinates
[xyCorE] Either xy or C or E (or E3) where
 xy is a Nx2 (or Nx3) matrix of x,y,(z) coordinates (equivalent to V)
 NOTE: only valid with A as the first input
 C is a NxN cost (perhaps distance) matrix, where C(I,J) contains the value of the cost to move from point I to point J
 NOTE: only valid with A as the first input
 E is a Px2 matrix containing a list of edge connections
 NOTE: only valid with V as the first input
 E3 is a Px3 matrix containing a list of edge connections in the first two columns and edge weights in the third column
 NOTE: only valid with V as the first input
[SID] (optional) 1xL vector of starting points. If unspecified, the algorithm will calculate the minimal path from all N points to the finish point(s) (automatically sets SID = 1:N)
[FID] (optional) 1xM vector of finish points. If unspecified, the algorithm will calculate the minimal path from the starting point(s) to all N points (automatically sets FID = 1:N)

Outputs:
[costs] is an LxM matrix of minimum cost values for the minimal paths
[paths] is an LxM cell containing the shortest path arrays

Note:
 If the inputs are [A,xy] or [V,E], the cost is assumed to be (and is calculated as) the point to point Euclidean distance
 If the inputs are [A,C] or [V,E3], the cost is obtained from either the C matrix or from the edge weights in the 3rd column of E3

Example:
 % Calculate the (all pairs) shortest distances and paths using [A,C] inputs
 n = 7; A = zeros(n); xy = 10*rand(n,2)
 tri = delaunay(xy(:,1),xy(:,2));
 I = tri(:); J = tri(:,[2 3 1]); J = J(:);
 IJ = I + n*(J-1); A(IJ) = 1
 a = (1:n); b = a(ones(n,1),:);
 C = round(reshape(sqrt(sum((xy(b,:) - xy(b',:)).^2,2)),n,n))
 [costs,paths] = dijkstra(A,C)

Example:
 % Calculate the shortest distance and path from point 3 to 5
 n = 15; A = zeros(n); xy = 10*rand(n,2)
 tri = delaunay(xy(:,1),xy(:,2));
 I = tri(:); J = tri(:,[2 3 1]); J = J(:);
 IJ = I + n*(J-1); A(IJ) = 1
 [cost,path] = dijkstra(A,xy,3,5)
 gplot(A,xy,'b.:'); hold on;
 plot(xy(path,1),xy(path,2),'ro-','LineWidth',2)
 for k = 1:n, text(xy(k,1),xy(k,2),[' ' num2str(k)],'Color','k'); end

Example:
 % Calculate the shortest distances and paths from the 3rd point to all the rest
 n = 7; V = 10*rand(n,2)
 I = delaunay(V(:,1),V(:,2));
 J = I(:,[2 3 1]); E = [I(:) J(:)]
 [costs,paths] = dijkstra(V,E,3)

Example:
 % Calculate the shortest distance and path from points [1 3 4] to [2 3 5 7]
 n = 7; V = 10*rand(n,2)
 I = delaunay(V(:,1),V(:,2));
 J = I(:,[2 3 1]); E = [I(:) J(:)]
 [costs,paths] = dijkstra(V,E,[1 3 4],[2 3 5 7])

Revision Notes:
(4/29/09) Previously, this code ignored edges that have a cost of zero, potentially producing an incorrect result when such a condition exists. I have solved this issue by using NaNs in the table rather than a sparse matrix of zeros. However, storing all of the NaNs requires more memory than a sparse matrix. This may be an issue for massive data sets, but only if there are one or more 0-cost edges, because a sparse matrix is still used if all of the costs are positive.

Acknowledgements

"All Pairs Shortest Path" Graph Solver and Dijkstra's Shortest Path Algorithm inspired this file.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (20)
16 Jul 2014 Pablo

This function works fine.
I call it many times as dijkstra(A,C,1) into an optimization function.
Nevertheless, the Matlab profiler halt me with warnings about the use of sparse functions, and indexing sparse matrices.

24 Mar 2014 Nguyen ThaiHoc  
21 Dec 2013 Joseph Kirk

@Dee, I am not sure what you are asking. There are several examples provided in the help notes (the comment section) that you can run from the Command Window to help you get started.

21 Dec 2013 Dee

I'm a beginner.Please tell me how to run this? Like, after the entire function the code using this function should be run or in between itself?

21 Jun 2013 Diego Flores

This function works perfectly for solving my Problem. thanks

01 Feb 2013 Sarhat

How to find a minimum cost path in Matlab. Something like this problem in C++
http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/
any idea please.......

27 Sep 2012 Joseph Kirk

Denny, could you email me with the specific inputs you used?

27 Sep 2012 Denny Milakara

I doesn't seem to be flawless. For four pairs of vertices only three routes has been successfully calculated on a triangulated 2-manifold with 134k of vertices and 267k of faces.

04 Apr 2012 Joseph Kirk

@David, this is not a bug in my implementation as much as a limitation of Dijkstra's Algorithm in general. You may have better luck looking for an algorithm that returns the k-best shortest paths.

29 Mar 2012 David B

The function works great except when two or more paths whose start and end nodes are the same are tied for shortest path. Then the function only returns one of the paths as shortest path. I am attempting to fix this, but I'm a beginner programmer, and its difficult for me to follow the steps in the algorithm. If you could fix this so that all paths whose length is equal to the shortest path length for a given start/end node are recorded, that would be wonderful and much appreciated!

07 Feb 2012 Jordan

Wonderful. Effective. Fast. Thank you for providing this very helpful code.

25 Oct 2011 ong wee kait

hey how do this thing works, i copy whole junk and paste it and it give me error

08 Jul 2011 Alexander Kosenkov  
06 Jul 2011 Shokoufeh

when I try to use the file I get the following error:
??? Undefined function or method 'dijkstra' for input arguments of type 'double'.

why this happens? thank you

14 Mar 2010 ratchapatnakhonsawan tangjittrong

good hello thank

21 Dec 2009 Jesse Blocher

Very well done - about 5x faster than my basic implementation. Thanks!
Recommend putting license in comment at bottom of code rather than as separate file. Easy to lose in a large /util directory.

20 Mar 2009 sun peng

Clear interface and detailed description. Good job! Very helpful!

13 Nov 2008 Sal

Hello Kirk...is there a way I can email you a question?

26 Oct 2008 Sal

Thank you I applied to a large graph and it handled it in record time...Good Job...

30 Jun 2008 thang vu

Thanks you, i apply it for an arborescent graph. It works perfectly.

Updates
01 May 2009

The code previously ignored edges that had a cost of zero. In such a case, the function sometimes produced an incorrect result. Zero-cost edges are now handled correctly.

Contact us