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

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.

Joseph Kirk (2021). Dijkstra's Minimum Cost Path Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/20025-dijkstra-s-minimum-cost-path-algorithm), MATLAB Central File Exchange. Retrieved .

Created with
R2014b

Compatible with any release

**Inspired by:**
"All Pairs Shortest Path" Graph Solver, Dijkstra's Shortest Path Algorithm

Find the treasures in MATLAB Central and discover how the community can help you!

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

marwan alasaliHi Sir,

if i run came error

>> dijkstra

Error using dijkstra (line 144)

Not enough input arguments.

marwan alasaliHi Sir,

if i run came this message

>> dijkstra

Error using dijkstra (line 144)

Not enough input arguments.

Yaoshen YuanThank you for sharing this! This toolbox is really helpful!

Antonio SmithHi Joseph,

Thank you for sharing the code.

I try to run the following example but I cannot successfully run it.

The error is Index exceeds array bounds.

Error in dijkstra (line 166)

path = path{1};

Could you please help me? Thank you very much.

% Example:

% % Calculate the shortest distance and path between two points

% n = 1000; A = zeros(n); xy = 10*rand(n,2);

% tri = delaunay(xy(:,1),xy(:,2));

% I = tri(:); J = tri(:,[2 3 1]); J = J(:);

% D = sqrt(sum((xy(I,:)-xy(J,:)).^2,2));

% I(D > 0.75,:) = []; J(D > 0.75,:) = [];

% IJ = I + n*(J-1); A(IJ) = 1;

% [cost,path] = dijkstra(A,xy,1,n)

% gplot(A,xy,'k.:'); hold on;

% plot(xy(path,1),xy(path,2),'ro-','LineWidth',2); hold off

% title(sprintf('Distance from %d to %d = %1.3f',1,n,cost))

SaniaMSaniaMThank you for your help.

But i am having a problem while using dijkstra syntax in matlab:

\\\\\ [cost,path]=dijkstra(A,C,1,4)

Undefined function or variable 'dijkstra'.

each time that i am trying to use dijkstra matlab syntax.its getting error. can you please help me?

Joseph Kirk@SaniaM, note the usage "[costs,paths] = dijkstra(A,C)" described in the help notes, where "C" is a cost matrix (and "A" is the adjacency matrix)

SaniaMHello.

I needed a help on finding the optimum path of a network from a Cost matrix .

Thank you.

kang yingYukiHi

How are the negative costs treated in this implementation?

Mahmoud SamiHi

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

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

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

CesarandMonaI 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

mohammad javad majidiJoseph 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.

HiWaveAbove 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 NguyenA =

(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{:}

HariHi,

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

Matt DelventhalJoseph,

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.

ghyslain butoyiooh 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?)

ghyslain butoyihi,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 XueJoseph 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 MoranWhy 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".

MaroWhen 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 DasGood to find SPF

minahi. 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 KirkRemove 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;

MohsenHi 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

PouriaJoseph KirkVishal, 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

Vishal GirisagarHi,

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.

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

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

DeeI'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 FloresThis function works perfectly for solving my Problem. thanks

SarhatHow 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 KirkDenny, could you email me with the specific inputs you used?

Denny MilakaraI 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 BThe 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!

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

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

Alexander KosenkovShokoufehwhen 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

ratchapatnakhonsawan tangjittronggood hello thank

Jesse BlocherVery 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 pengClear interface and detailed description. Good job! Very helpful!

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

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

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