Code covered by the BSD License  

Highlights from
Dijkstra's Minimum Cost Path Algorithm

4.91667
4.9 | 12 ratings Rate this file 117 Downloads (last 30 days) File Size: 10.6 KB File ID: #20025 Version: 1.2
image thumbnail

Dijkstra's Minimum Cost Path Algorithm

by

Joseph Kirk (view profile)

 

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
[showWaitbar] (optional) a scalar logical that initializes a waitbar if nonzero

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:
(3/13/15) 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.

Acknowledgements

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

MATLAB release MATLAB 8.4 (R2014b)
MATLAB Search Path
/
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (29)
01 May 2015 Joseph Kirk

Joseph Kirk (view profile)

@Maro, it is possible you are using an older version of MATLAB that does not allow the ~ notation for ignoring function outputs. Try replacing the "~" on Line 250 with an unused variable name like "ignore".

Comment only
29 Apr 2015 Maro

Maro (view profile)

When I run one the first example in the file
% Calculate the (all pairs) shortest distances and paths using [A,xy] 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
% [costs,paths] = dijkstra(A,xy)

I got the error
??? Error: File: dijkstra.m Line: 250 Column: 19
Expression or statement is incorrect--possibly
unbalanced (, {, or [.

Comment only
20 Apr 2015 S Das

S Das (view profile)

Good to find SPF

Comment only
06 Apr 2015 mina

mina (view profile)

hi. i want to make a WSN and implement one of the intelligent routing protocols on it.for start i dont know how to simulate a WSN. would anyone help me or send me anything helpful?
thank you

Comment only
06 Nov 2014 Joseph Kirk

Joseph Kirk (view profile)

Remove the edge connections in the adjacency matrix for any nodes that are inside the "keep out" area prior to running the shortest path algorithm:

A(in,:) = 0;
A(:,in) = 0;

Comment only
06 Nov 2014 Mohsen

Mohsen (view profile)

Hi Joseph,
I am using the code below to define a grid and find the shortest point between two points. I am also defining a polygon as a keep out area. How can I change the cost of the paths inside the polygon so that the connection line goes around the keep out are?
I have Identified the points that are inside the polygon.
Please advice.
Thanks
Mohsen

clear all;close all;
[xgrid ygrid]= meshgrid (-5:0.5:5,-5:0.5:5);
ygrid(:,2:2:end)=ygrid(:,2:2:end)+0.25;
xx=xgrid(1:end);
yy=ygrid(1:end);

xy=[xx;yy]';

L = linspace(0,2.*pi,11); xv = 3*sin(L);yv = 3*cos(L);
plot(xv,yv,'g')
hold on
in = inpolygon(xx,yy,xv,yv);
plot(xy(find(in==1),1),xy(find(in==1),2),'om')

% xy(find(in==1),:)=-5;
n = size(xy,1); 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,437) ;
gplot(A,xy,'k.:'); 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

21 Oct 2014 Pouria

Pouria (view profile)

 
08 Oct 2014 Joseph Kirk

Joseph Kirk (view profile)

Vishal, in your case, you could provide the inputs as follows:

C = zeros(4);
C(1,2) = 10;
C(1,3) = 20;
C(2,4) = 30;
C(3,4) = 40;
A = logical(C);
[cost,path] = dijkstra(A,C,1,4)

And the output you would get is:

cost =
40
path =
1 2 4

Comment only
08 Oct 2014 Vishal Girisagar

Hi,
I need to use this. I am getting confused with the input form that should be given.
For ex:

I have 4 simple nodes.

1 2 3 4

1->2: weight = 10
1->3: weight = 20
2->4: weight = 30
3->4: weight = 40

i need to find path from 1 to 4.

Can you tell me how to give input.

Comment only
16 Jul 2014 Pablo

Pablo (view profile)

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

Joseph Kirk (view profile)

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

Comment only
21 Dec 2013 Dee

Dee (view profile)

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?

Comment only
21 Jun 2013 Diego Flores

This function works perfectly for solving my Problem. thanks

01 Feb 2013 Sarhat

Sarhat (view profile)

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

Comment only
27 Sep 2012 Joseph Kirk

Joseph Kirk (view profile)

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

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

Comment only
04 Apr 2012 Joseph Kirk

Joseph Kirk (view profile)

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

Comment only
29 Mar 2012 David B

David B (view profile)

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!

Comment only
07 Feb 2012 Jordan

Jordan (view profile)

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

Comment only
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

Comment only
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

sun peng (view profile)

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

13 Nov 2008 Sal

Sal (view profile)

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

Comment only
26 Oct 2008 Sal

Sal (view profile)

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 1.1

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.

13 Mar 2015 1.2

Cleaned up several sparse matrix MLINT messages.

Contact us