Scripts Index
Tools and Utilities Development Tools  

Advanced Dijkstra's Minimum Path Algorithm

download download home home   report broken
important script information
company name:
Joseph Kirk
license: Shareware
minimum requirements: MATLAB 7.6 (R2008a)
functional limitations:
Advanced Dijkstra's Minimum Path Algorithm description
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.
Similar scripts
Rob Keyboard (Popularity: ) : This plugin is produced for holding on keyboard when pairing program. You can type "shift ctrl K" to lock intellJ by a Dialog with amusing words. You can lock intellJ by password, with configging password enabled.At first, you should add ...
CIE Coordinate Calculator (Popularity: ) : This software is for calculating the CIE chromaticity co-ordinates of phosphor materials using the photo luminescence data. The software also shows the position of the co-ordinates in chromaticity diagram and expected color of the material. Please note that the color ...
New Dream Coder for Oracle (Popularity: ) : This tool is an code generator for Oracle. While fetching large tables this tool reduces usage of memory. Some features of this tool are, it has new password ecryption, procedure builder, session monitor, SQL templates etc., It increases execution times ...
Foreign Exchange Options (Popularity: ) : fxoptions( S0, X, rd, rf, T, vol, style)Valuation of European and American call and put options on foreign exchange using Garman-Kohlhagen model.European option prices are given by an exact formula (Garman-Kohlhagen).American option prices are approximated using both binomial and trinomial ...
Anti Cut and Paste (Popularity: ) : This utility is helpful for programmers that allows them to search programming language source code's text fragments which have been copied and pasted. Some key features of this tool are, this tool supports both command line and Graphical User Interface ...
AC Protect Standard (Popularity: ) : This utility is used for avoiding hackers from cracking your software using special techniques called anti crack. It works with all windows platforms. Some features of this tool are, this tool compresses ocx, scr, exe, dll and more, dynamic encrypt ...
Bokai Barcode Image generator (Popularity: ) : This tool is used for barcode generator and which has an ActiveX control for printing barcodes. This tool contains more than twenty five barcode types. This tool supports only ActiveX control programs. Users can customize barcode parameters and design of ...
VBcodePrint (Popularity: ) : This Add-In to Microsoft Visual Basic 6 significantly enhances its source code printing capabilities. You can print any part of your VB project's source code from within the VB's development environment. / You can create and save your own output ...
Use Matlab Editor to Write and Run Ansys Program. (Popularity: ) : You don't have to switch your screen between Matlab, Ansys and UltraEdit or PSPad anymore, when you doing FEM-Analysis.You can use MEditor to write your Ansys APDL program and use the excellent feature of MEditor to structure your Code: Cell-Function, ...
VBAcodePrint (Popularity: ) : This add-in enables you to print Microsoft VBA source code in color of your applications across the entire Microsoft Office 2000 suite of applications: Word, Excel, Outlook, Access, PowerPoint, and FrontPage and any other VBA enabled software. / You can ...
User reviews

Write a review:
1 2 3 4 5 6 7 8 9 10
1=poor 10=excellent
Write review*
Your name*
Email*
  (Comments are moderated, and will not appear on this site until the editor has approved them)
 
Similar Software
SolitaireCryptoDemo (Popularity: ) : SolitaireCryptoDemo is a visual demonstration of the steps involved in generating a keystream using Bruce Schneier's Solitaire encryption algorithm.

Featuring smooth animations and descriptions of all steps.

Example Instructions:

Start demo with "python SolitaireCrypto.py". Press "Space" to continue to the next step. Press ...

Mupen64Plus (Popularity: ) : Mupen64Plus is a cross-platform plugin-based N64 emulator which is capable of accurately playing many games. Included are four MIPS R4300 CPU emulators, with dynamic recompilers for 32-bit x86 and 64-bit amd64 systems, and necessary plugins for audio, graphical rendering (RDP), ...
Repair WAB Tool (Popularity: ) : Repair WAB Tool is the ultimate answer to the burning question of how to repair wab address book files and recover your lost address book contacts. Repair WAB Tool is a state of the art error detection and file recovery ...
InstallAware Setup Squeezer for MSI (Popularity: ) : Now with Setup Squeezer for Windows Installer and Setup Squeezer for InstallShield, you can take advantage of InstallAware`s industry-leading package compression - without having to migrate your setup projects. Setup Squeezer offers : * Simplicity - a very simple wizard ...
Cisdem DataRecovery for Mac (Popularity: ) : Using advanced scanning technology and directory restructuring algorithm, Cisdem DataRecovery for Mac can help you to recover lost valuable data, documents, emails, videos, music, photos, and lost partitions from any Mac supported data storage media, including internal/external hard drives, USB drives, SD ...
dotConnect for Oracle (Popularity: ) : dotConnect for Oracle is an enhanced data provider built over ADO.NET architecture and a development framework with a number of innovative technologies. With state of the art ORM solutions such as Entity Framework and LinqConnect, it introduces new approaches for ...
Cisdem Data Recovery for Mac 4.0.0 (Popularity: ) : Using advanced scanning technology and directory restructuring algorithm, Cisdem Data Recovery for Mac can help you to recover lost valuable data, documents, emails, videos, music, photos, and lost partitions from any Mac supported data storage media, including internal/external hard drives, USB drives, ...
ConversionTrack (Popularity: ) : According to the web log, ConversionTrack can analyze every user's access path, and generate professional report on visitor's conversion rates. It can help you better understand the behavior of web visitors, be more accurate to evaluate all kind of online ...
Advance System Optimizer (Popularity: ) : Advanced System Optimizer's system files backup and restore functions keep your critical files secure so that you can restore them if you suffer a system failure. You can back up your Windows registry and restore it if your registry is ...
Encryptafile (Popularity: ) : Encryptafile is an application that allows you to encrypt and decrypt data using the latest industry standard strong encryption algorithms. The application supports both traditional secret-key encryption as well as public-key encryption. For traditional strong encryption, Encryptafile supports the newly ...
ad


Rate me
supported os
Linux
Mac OSX
Macintosh
Win All, BSD, Solaris
stats
downloads 7
version 1.0
size in Kb 10
popularity   
519/370730
user rating 5/10
New Scripts
Popular Scripts
Latest Reviews