File Exchange

image thumbnail

Dijkstra's Minimum Cost Path Algorithm

version 1.2 (10.6 KB) by

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

4.94118
17 Ratings

83 Downloads

Updated

View License

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.

Comments and Ratings (45)

Joseph Kirk

Joseph Kirk (view profile)

@Kevin, double-check your cost matrix. The result cannot be 1-3-6-5 when there is no edge connection between 6 and 5.

Kevin Nguyen

A =
   (1,2) 7
   (1,3) 9
   (2,3) 10
   (2,4) 15
   (3,4) 11
   (4,5) 6
   (1,6) 14
   (3,6) 2

cost = 26
path = 1 3 4 5

The result should be 1-3-6-5 with cost of 20.
Is there something wrong?
Thanks!

RamenYum!

Hello, I'm trying to use this algorithm on a train system. I'm sorry for asking a basic question. If I want to use an Edge list as my input, what is V supposed to be?

I'm obviously not an expert here. I'd appreciate any help you all can give me.

Thank you in advance.

Joseph Kirk

Joseph Kirk (view profile)

@Hari, to see the paths in a list, you could type >> paths{:}

Hari

Hari (view profile)

Hi,
I wanted to get the shortest path and costs between all pairs of nodes.
This was my input : [costs, paths] = dijkstra(A,C,[1:3],[1:3])

The output I got was:
costs =

     0 8 10
   Inf 0 2
   Inf 2 0

paths =

    [ 1] [1x2 double] [1x3 double]
    [NaN] [ 2] [1x2 double]
    [NaN] [1x2 double] [ 3]

Is it possible to list all paths

Cai Gao

AvatarChen

Good job!

Joseph Kirk

Joseph Kirk (view profile)

@Matt, it does.

There are multiple ways the inputs can be provided. You can either (1) pass in an adjacency matrix and XY points, (2) pass in an adjacency matrix and cost matrix, (3) pass in XY points and an edge list, or (4) pass in XY points and an edge list with a third column that has the edge costs. Note that all of this information is in the help notes.

Joseph,

This is a nice function, seems to work well with not-too-big graphs. It would be nice if it could work with just a list of connections plus a list of costs. As is, the requirement for an NxN adjacency matrix and an NxN matrix of costs makes it impossible to use for graphs above a certain number of nodes (like 10000 or so).

Joseph Kirk

Joseph Kirk (view profile)

@ghyslain, even if your A matrix is sparse, if you request the all-pairs shortest paths (by not providing start/finish inputs) then the code attempts to build a non-sparse NxN matrix to store all of the output costs/paths. So if you only need the shortest path from, say, node 768 to 5923, you can pass the start/finish ids in as an input. That should significantly reduce the memory requirements of my function.

ooh ok
its a lot my matrix A=7288*7288
is there like a trick to use less memory?

Joseph Kirk

Joseph Kirk (view profile)

@ghyslain, based on the "Out of memory" error message, the problem is not a bug in the code. Rather, it has to do with the limitations of your machine. What is the size of your input graph? (i.e. How many nodes are you trying to process?)

hi,i ran ur code..
this is the error i got can u help me

Out of memory. Type HELP MEMORY for your options.

Error in num2cell (line 34)
        c{i} = a(i);

Error in dijkstra (line 53)
    paths = num2cell(NaN(L,M));

Martin Xue

Joseph Kirk

Joseph Kirk (view profile)

@Daniel, thank you for you interest in my code. You have an interesting point, but you may wish to consider that:
 
1. I designed my function to work using a variety of formats for specifying edge connections and edge costs, and in many of the supported cases, the information is best represented by a pair of variables -- so the input interface would have been much more complex had I also chosen to allow a variable number of inputs to represent them.
 
2. I can imagine a case where an edge connection exists but the cost may still be zero. In other words, just because your particular problem may simplify down to such a relationship between the adjacency matrix and cost matrix does not mean that it is a good assumption to make in general, nor one to force upon every user.
 
For these reasons, I would contend that my function has the greatest amount of usefulness to the community as is, with the adjacency matrix explicitly defined and with a cost matrix provided separately.

Daniel Moran

Why is the adjacency matrix needed if a cost matrix is provided? In that case the adjacency matrix is simply C>0, right?

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

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

S Das

S Das (view profile)

Good to find SPF

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

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;

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

Pouria

Pouria (view profile)

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

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.

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.

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.

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?

Diego Flores

This function works perfectly for solving my Problem. thanks

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

Joseph Kirk

Joseph Kirk (view profile)

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

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.

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.

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!

Jordan

Jordan (view profile)

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

ong wee kait

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

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

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.

sun peng

sun peng (view profile)

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

Sal

Sal (view profile)

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

Sal

Sal (view profile)

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

thang vu

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

Updates

1.2

Cleaned up several sparse matrix MLINT messages.

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.

MATLAB Release
MATLAB 8.4 (R2014b)

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

» Watch video