Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

# Advanced Dijkstra's Minimum Path Algorithm 1.0

Date Added: July 13, 2013  |  Visits: 195

DIJKSTRA Calculate Minimum Costs and Paths using Dijkstra's AlgorithmInputs:[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 arraysNote: 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 E3Example: % 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'); endExample: % 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.

 Requirements: No special requirements Platforms: Matlab Keyword: Costpath,  Costspaths,  Dijkstraac,  Dijkstraaxy,  Dijkstrave,  Gplotaxy,  Notes,  Num Strk Color,  Revision,  Textxyk Xyk Users rating: 0/10