Code covered by the BSD License

### Highlights from Advanced Dijkstra's Minimum Path Algorithm

5.0

5.0 | 8 ratings Rate this file 61 Downloads (last 30 days) File Size: 3.92 KB File ID: #20025

# Advanced Dijkstra's Minimum Path Algorithm

22 May 2008 (Updated )

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

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)
21 Dec 2013

@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

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

This function works perfectly for solving my Problem. thanks

01 Feb 2013

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/

27 Sep 2012

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

27 Sep 2012

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

@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

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

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

25 Oct 2011

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

08 Jul 2011
06 Jul 2011

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

good hello thank

21 Dec 2009

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

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

13 Nov 2008

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

26 Oct 2008

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

30 Jun 2008

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