4.1 | 13 ratings Rate this file 226 downloads (last 30 days) File Size: 3.43 KB File ID: #12850

Dijkstra's Shortest Path Algorithm

by Joseph Kirk

01 Nov 2006 (Updated 21 May 2007)

Code covered by BSD License

calculates the shortest path and distance between two nodes on a map

Download Now | Watch this File

File Information

Description

This function can
1. Find the shortest path and distance from a starting node to an ending node on a map**
2. Find the shortest paths and distances from a starting node to ALL other nodes on a map**

**The map should consist of nodes and segments, such that:
1. nodes have the format [ID X Y] or [ID X Y Z] (with ID being an integer, and X,Y,Z representing position coordinates and of type double)
2. segments have the format [ID N1 N2] (with ID being an integer, and N1 N2 representing IDs from the nodes list such that there is an [undirected] edge/segment between node N1 and node N2, and obviously of integer type also)

Note:
The function generates a random map of nodes and segments that it uses if no inputs are given. This way, it acts like a script if it is run with no inputs, and it acts like a function otherwise.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Dijkstra Shortest Path Routing
This submission has inspired the following:
Advanced Dijkstra's Minimum Path Algorithm

MATLAB release

MATLAB 7.3 (R2006b)

Tags for This File
Everyone's Tags	dijkstra, graph, map, shortest distance, shortest path(2)
Tags I've Applied
Add New Tags	Please login to tag files.

Comments and Ratings (15)
02 Jan 2007	Daren O'Connor	Great! Fast, efficient, and easy to use.
08 Feb 2007	titin siburian	i think this program is really good.
13 Apr 2007	han daza	works like a charm!! quite fast, in my case 342 nodes (708 segments) ~ 0.3 secs. it even works if the nodes you feed in are not all used by the segments !! thanks
31 May 2007	Bandi Reddy
28 Jun 2007	Omer KAMAL	can u make it for 7 nodes to see the output.
07 Sep 2007	Chuthamart Panklin
07 Sep 2007	The Author	Chuthamart - If you're going to give a rating of 1, an explanation would be nice...
08 Oct 2007	Nikhil M	Very Good; Thanks;
14 Oct 2007	Charles Kingston	This already exist in one of the matlab demos.
10 Dec 2007	ioannis tsolakidis
18 Jun 2008	Kuba Wu
01 Dec 2008	Weihao Yin
04 May 2009	Michael Ashby	Very useful code for finding the distances from a given node to all the others. Thanks to the author for assistance and updates.
28 May 2009	abdullah rfdgsdf	Perfect >> thank u man ... go head
29 Sep 2009	Benjamin Knight	Great code, well documented and easy to apply. Note that I needed to transpose A and C matrices to get a result from this function.

Please login to add a comment or rating.

Updates
09 Jan 2007	Combined script and function into a single m-file that can be run "as is" or with user specified inputs.
21 May 2007	Improved m-file and help notes.

Tag Activity for this File
Tag	Applied By	Date/Time
dijkstra	Joseph Kirk	22 Oct 2008 08:46:43
shortest path	Joseph Kirk	22 Oct 2008 08:46:43
shortest distance	Joseph Kirk	22 Oct 2008 08:46:43
map	Joseph Kirk	22 Oct 2008 08:46:43
graph	Joseph Kirk	22 Oct 2008 08:46:43
shortest path	Amit kumar	14 Jun 2009 14:15:00

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.