| 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
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:
(4/29/09) 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. However, storing all of the NaNs requires more memory than a sparse matrix. This may be an issue for massive data sets, but only if there are one or more 0-cost edges, because a sparse matrix is still used if all of the costs are positive. |
