Code covered by the BSD License  

Highlights from
Dijkstra's Shortest Path Algorithm

4.2

4.2 | 15 ratings Rate this file 100 Downloads (last 30 days) File Size: 3.43 KB File ID: #12850
image thumbnail

Dijkstra's Shortest Path Algorithm

by Joseph Kirk

 

01 Nov 2006 (Updated 21 May 2007)

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

| 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

Dijkstra Shortest Path Routing inspired this file.

This file inspired Advanced Dijkstra's Minimum Path Algorithm.

MATLAB release MATLAB 7.3 (R2006b)
Tags for This File  
Everyone's Tags
dijkstra(7), graph(3), map(2), shortest distance, shortest path(2)
Tags I've Applied
Add New Tags Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (18)
12 Sep 2012 Andrea  
09 Aug 2012 Jesus Luevano

Hi, when I try to use the algorithm to optimization route, always it asks me the segments from the nodes, what happens if I do not know them, because I trying to get the optmization route of an image.

by the way, I do not understand the CMatrix relationship with the real image on the biograph function.

06 Mar 2012 Xilu Wang  
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.

28 May 2009 abdullah rfdgsdf

Perfect >> thank u man ... go head

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.

01 Dec 2008 Weihao Yin  
18 Jun 2008 Kuba Wu  
10 Dec 2007 ioannis tsolakidis  
14 Oct 2007 Charles Kingston

This already exist in one of the matlab demos.

08 Oct 2007 Nikhil M

Very Good; Thanks;

07 Sep 2007 The Author

Chuthamart - If you're going to give a rating of 1, an explanation would be nice...

07 Sep 2007 Chuthamart Panklin  
28 Jun 2007 Omer KAMAL

can u make it for 7 nodes to see the output.

31 May 2007 Bandi Reddy  
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

08 Feb 2007 titin siburian

i think this program is really good.

02 Jan 2007 Daren O'Connor

Great! Fast, efficient, and easy to use.

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.

Contact us