Search
Code Directory
 ASP
 ASP.NET
 C/C++
 CFML
 CGI/PERL
 Delphi
 Development
 Flash
 HTML
 Java
 JavaScript
 Pascal
 PHP
 Python
 SQL
 Tools
 Visual Basic & VB.NET
 XML
New Code
dbForge Studio for PostgreSQL 2.3.212
HTMLPad 2020 16.2
WeBuilder 2020 16.2
Rapid CSS 2020 16.2
Rapid PHP 2020 16.2
C# HTML to PDF 2020.8.1
Flowrigami 1.0.0.1
Vue Injector 3.3
Spectrum Analyzer pro Live 2019
Devart Excel Add-in for HubSpot 2.1
RentALLScript - Airbnb clone 2.2
SuiteCRM Theme Customization 7.11.6
iScripts NetMenus 3.1
iScripts EasyIndex 2.2
iScripts EasySnaps 2.0
Top Code
IcrediBB Bulletin Board System 1.0
Uber Clone with Safety Measure Addons 2.0
HTMLPad 2020 16.2
Extreme Injector 3.7
MLM Unilevel Plan Software 1.0.2
Anteil open source CRM 1.I
Tadpoles .0.1
Shop Management CRM 1
HomepageSearchEngine 3.0
PHP Search Engine (SEARCpHp)
Video Conference Website Scripts 2.86
Flash Games Page 1.0.5
LMS Algorithm Demonstration 1.0
Ether MMORPG 0.1
Audit Trail 1.1.12
Top Rated
Uber Clone with Safety Measure Addons 2.0
Answers phpSoftPro 3.12
phpEnter 5.1.
Quick Maps For Dynamics CRM 3.1
Single Leg MLM 1.2.1
Azizi search engine script PHP 4.1.10
Paste phpSoftPro 1.4.1
Extreme Injector 3.7
Apphitect Airbnb Clone Script 1.0
Deals and Discounts Website Script 1.0.2
Pro MLM 1
Solid File System OS edition 5.1
Classified Ad Lister 1.0
Aglowsoft SQL Query Tools 8.2
Invoice Manager by PHPJabbers 3.0
Advanced Dijkstra's Minimum Path Algorithm 1.0
File ID: 81368






Advanced Dijkstra's Minimum Path Algorithm 1.0
Download Advanced Dijkstra's Minimum Path Algorithm 1.0http://www.mathworks.com/Report Error Link
License: Shareware
File Size: 10.0 KB
Downloads: 36
Submit Rating:
Advanced Dijkstra's Minimum Path Algorithm 1.0 Description
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.

License: Shareware

Related: dijkstraaxy, gplotaxy, costpath, dijkstraac, costspaths, textxyk xyk, num strk color, Revision, Notes, dijkstrave

O/S:BSD, Linux, Solaris, Mac OS X

File Size: 10.0 KB

Downloads: 36



More Similar Code

Dijkstra shortest path algorithm.



A-star (A*) Shortest Path Algorithm



This function is based on Yen's k-Shortest Path algorithm (1971)
It retuns:
1) [shortestPaths]: the list of K shortest paths (in cell array 1xK)
2) [totalCosts] : costs of the K shortest paths (in array 1xK)
Yen's algorithm...



Dijkstra(G,s) finds all shortest paths from s to each other vertex in the graph, and shortestPath(G,s,t) uses Dijkstra to find the shortest path from s to t. Uses the priorityDictionary data structure (Recipe 117228) to keep track of estimated...



A Ruby implementation of Dijkstra's Shunting Yard Algorithm, for converting tokens from infix notation to postfix notation (aka Reverse Polish Notation).



The union find data structure is primarily used for Kruskal's Minimum Spanning Tree algorithm, though can be used whenever one only needs to determine of two items are in the same set, and be able to combine sets quickly.



Returns Rissanen's Minimum Description Length.
Requires System Identification toolbox.
Call it like built-in functions aic(m) and fpe(m).
Use MDL like AIC or FPE to compare models of different complexities. Choose model with lowest...



A simple Bayesian Network example for exact probabilistic inference using Pearl's message-passing algorithm on singly connected graphs.



This is a MATLAB version of Jerome Friedman's 1984 supersmoother algorithm. The original was written in Fortran; this is a vectorized translation. The algorithm is a variable span smoother which uses cross validation to pick the best span for each...



Sudoku Solver - A generic implementation of Donald Knuth's Dancing Links algorithm and a number of techniques, translated into rules, implemented in JESS.

User Review for Advanced Dijkstra's Minimum Path Algorithm
- required fields
     

Please enter text on the image