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*(J1); 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*(J1); 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.
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. Zerocost edges are now handled correctly. 
Inspired by: "All Pairs Shortest Path" Graph Solver, Dijkstra's Shortest Path Algorithm
Create scripts with code, output, and formatted text in a single executable document.
kang ying (view profile)
Yuki (view profile)
Hi
How are the negative costs treated in this implementation?
Mahmoud Sami (view profile)
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 (view profile)
Joseph Kirk (view profile)
@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 (view profile)
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, 191197, 1966), but have't found out any codes that can realise it. Please advise. Thank you very much!
Joseph Kirk (view profile)
@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 QUINQUENEL (view profile)
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! (view profile)
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 (view profile)
Joseph Kirk (view profile)
@CesarandMona, the matrix C is the cost matrix, while A is an adjacency matrix that specifies valid edges. If there is a nonzero 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 (view profile)
I benefit a lot from your code. Thanks.
Could you please give more detail about the matrix C? Why does C have a nonzero 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*(J1); 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 majidi (view profile)
Joseph Kirk (view profile)
@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 "NbyMbyP". So E is an array that has any number of rows but 2 columns.
Troy (view profile)
Above it says "E is a Px2" but give no definition of P
Joseph Kirk (view profile)
@Kevin, doublecheck your cost matrix. The result cannot be 1365 when there is no edge connection between 6 and 5.
Kevin Nguyen (view profile)
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 1365 with cost of 20.
Is there something wrong?
Thanks!
RamenYum! (view profile)
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 (view profile)
@Hari, to see the paths in a list, you could type >> paths{:}
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 (view profile)
AvatarChen (view profile)
Good job!
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.
Matt Delventhal (view profile)
Joseph,
This is a nice function, seems to work well with nottoobig 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 (view profile)
@ghyslain, even if your A matrix is sparse, if you request the allpairs shortest paths (by not providing start/finish inputs) then the code attempts to build a nonsparse 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 butoyi (view profile)
ooh ok
its a lot my matrix A=7288*7288
is there like a trick to use less memory?
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?)
ghyslain butoyi (view profile)
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 (view profile)
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 (view profile)
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 (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 (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*(J1); A(IJ) = 1
% [costs,paths] = dijkstra(A,xy)
I got the error
??? Error: File: dijkstra.m Line: 250 Column: 19
Expression or statement is incorrectpossibly
unbalanced (, {, or [.
S Das (view profile)
Good to find SPF
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 (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 (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*(J1); 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 (view profile)
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
Vishal Girisagar (view profile)
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 (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.
Nguyen ThaiHoc (view profile)
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 (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 (view profile)
This function works perfectly for solving my Problem. thanks
Sarhat (view profile)
How to find a minimum cost path in Matlab. Something like this problem in C++
http://www.geeksforgeeks.org/dynamicprogrammingset6mincostpath/
any idea please.......
Joseph Kirk (view profile)
Denny, could you email me with the specific inputs you used?
Denny Milakara (view profile)
I doesn't seem to be flawless. For four pairs of vertices only three routes has been successfully calculated on a triangulated 2manifold with 134k of vertices and 267k of faces.
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 kbest shortest paths.
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 (view profile)
Wonderful. Effective. Fast. Thank you for providing this very helpful code.
ong wee kait (view profile)
hey how do this thing works, i copy whole junk and paste it and it give me error
Alexander Kosenkov (view profile)
Shokoufeh (view profile)
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
ratchapatnakhonsawan tangjittrong (view profile)
good hello thank
Jesse Blocher (view profile)
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 (view profile)
Clear interface and detailed description. Good job! Very helpful!
Sal (view profile)
Hello Kirk...is there a way I can email you a question?
Sal (view profile)
Thank you I applied to a large graph and it handled it in record time...Good Job...
Thanks you, i apply it for an arborescent graph. It works perfectly.