File Exchange

image thumbnail

Dijkstra's Minimum Cost Path Algorithm

version 1.2.0.0 (10.6 KB) by Joseph Kirk
calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm

70 Downloads

Updated 13 Mar 2015

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 (60)

kang ying

Yuki

Yuki (view profile)

Hi
How are the negative costs treated in this implementation?

Mahmoud Sami

Hi
I need to ask about "D" what is it mean? what is it's math eq.? and why it differ from one sample to another?.
The other thing how to make the code containing "V" working for a 3D model.

David Franco

Joseph Kirk

@Yan, if it were me, I would add another variable that contains the sum of toll costs for each path as the algorithm progresses. Then once the cost exceeds the constraint, set the path distance equal to infinity.

Yan Wang

Hi Joseph, I have a question: someone wants to drive a car from a fixed starting node in a large road network (directioned). The weight of an edge that connects two adjacent nodes is the distance between them. The driver is not allowed to pass the same edge twice. In reaching every node (except the starting and terminal node) the driver need to pay a toll fee, which is assigned in priori but not necessarily dependant on the distance. The driver has a certain amount of money to pay the toll. The question is how to design the route so that the driver can drive as far as possible in this network. This is to maximise the distance with the constraint of the total toll fees. I wonder if one can solve this constrained optimisation problem with your algorithms. We found there is algorithm described by Joksch (Journal of Mathematical analysis and applications 14, 191-197, 1966), but have't found out any codes that can realise it. Please advise. Thank you very much!

Joseph Kirk

@Antoine, sure, just pass in the ID of your starting node for the SID input and an array of IDs for the destination nodes as the FID input. Similar examples are given in the help notes.

Hi Joseph,

I need to find the shortest path starting from a single node reaching several other nodes in one row.
Do you know how can I achieve this?

Thank you in advance.

RamenYum!

Joe, thank you for this code. I am using it to support my research and I need to cite you.

How would you want this work to be cited? I am using APA v6.

Thank you in advance.

indu

indu (view profile)

Joseph Kirk

@CesarandMona, the matrix C is the cost matrix, while A is an adjacency matrix that specifies valid edges. If there is a non-zero element in C but the corresponding entry in A is not a valid edge, it will just be ignored. The code you referenced is just a simple example I provided in the help notes. If you want to be particular, you can force the costs to be infinite after the original calculation for C:
>> C(~A) = Inf
But the final result will be the same regardless.

CesarandMona

I benefit a lot from your code. Thanks.
Could you please give more detail about the matrix C? Why does C have a non-zero element at the position in which A has a 0 element in your code below? For example, A(1,7) and C(1,7).

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)

A =

0 0 0 1 0 1 1
1 0 0 0 0 0 1
0 1 0 0 1 0 1
1 0 0 0 1 1 1
0 0 1 1 0 1 1
0 0 1 1 1 0 0
1 1 1 1 1 0 0

C =

0 10 10 7 7 7 4
10 0 3 8 7 8 7
10 3 0 6 4 6 6
7 8 6 0 1 1 4
7 7 4 1 0 2 4
7 8 6 1 2 0 5
4 7 6 4 4 5 0

Joseph Kirk

@Troy, P is just a number to indicate the size, like saying "Nx2" or "Mx3". See the help notes for "meshgrid" which can have 3D matrices and it describes their dimensions as being "N-by-M-by-P". So E is an array that has any number of rows but 2 columns.

Troy

Troy (view profile)

Above it says "E is a Px2" but give no definition of P

Joseph Kirk

@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

@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

@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

@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

@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

@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

@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

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

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

@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

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

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

Cleaned up several sparse matrix MLINT messages.

1.1.0.0

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 Compatibility
Created with R2014b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.


Learn About Live Editor