View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Dijkstra's Shortest Path Algorithm

4.3 | 23 ratings Rate this file 161 Downloads (last 30 days) File Size: 3.43 KB File ID: #12850 Version: 1.0
image thumbnail

Dijkstra's Shortest Path Algorithm


Joseph Kirk (view profile)


01 Nov 2006 (Updated )

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

| Watch this File

File Information

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)

    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.


Dijkstra Shortest Path Routing inspired this file.

This file inspired Dijkstra's Minimum Cost Path Algorithm.

MATLAB release MATLAB 7.3 (R2006b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (38)
24 Dec 2016 Fayez Talmees

Thank You Joseph Kirk

26 Nov 2016 Joseph Kirk

Joseph Kirk (view profile)

@Andrea, you may wish to try this version:

Comment only
25 Nov 2016 Andrea

Andrea (view profile)

can this be generalized to the directed case?

Comment only
10 Jun 2016 taurusong song

18 Apr 2016 Analeze Erica

13 Apr 2016 Rick Hill

Rick Hill (view profile)

Thank you for your algorithm, it has been very helpful. Do you know the complexity (big O notation) of your algorithm?

Comment only
13 Apr 2016 Rick Hill

Rick Hill (view profile)

07 Apr 2016 hgl

hgl (view profile)

great work!!

24 Nov 2015 Hatim Salih

Great work.

11 Nov 2015 mel Samia

i think this program is really good.

Comment only
29 Oct 2015 rajat soni

09 Sep 2015 Ronan

Ronan (view profile)

@Joseph Kirk I looked at other examples that auto connected links to every node but now Iv realised I actually needed to manually specify the segments, so your solution is much preferred. I got it working the way I wanted. Thank you very much.

Comment only
08 Sep 2015 Joseph Kirk

Joseph Kirk (view profile)

@Ronan, there is a way, yes, but without knowing the specifics of your problem it is difficult to guess where you are having issues.

However, you might try using this version of Dijkstra's Algorithm first to see if it is more intuitive:

By the way, I am not sure why you say you have to generate the segments manually - because the whole point of Dijkstra's algorithm is to find shortest paths in a graph, which (by definition) consists of nodes/vertices and segments/edges - so if you do not already have nodes and segments defined, it is unclear why you are trying to use this function at all.

Comment only
07 Sep 2015 Ronan

Ronan (view profile)

is there an example for getting the shortest paths from starting node to ALL other nodes? I was able to run the example included in the script but it seems that I have to generate the segments manually.

Comment only
08 Oct 2014 Vishal Girisagar

I need to use this. I am getting confused with the input form that should be given.
For ex:

I have 4 simple nodes.

1 2 3 4

1->2: weight = 10
1->3: weight = 20
2->4: weight = 30
3->4: weight = 40

i need to find path from 1 to 4.

Can you tell me how to give input.

Comment only
31 May 2014 Puffeltje

I have a database with nodes en segments but the segments must be calculated before they can be added to the algorithm. I have a query wich calculates all the posible segments from one specific node to other nodes.

Is it possible to calculate the needed segments during the algorithm? In that case i don't have to calculate all the possible segments for the whole database (16,000 nodes with about 2,450,000 segments)


31 May 2014 Sunil

Sunil (view profile)

Hi All,

I have a need, wherein there are multiple nodes spread across. All I know is the location of each nodes. How do I find the best path from all nodes to a particular node?

Can I use the "Dijkstra's Shortest Path Algorithm"? Believe, its YES.

I am not sure, as how do I populate the variable, “segments” in program.

Appreciate an earlier response on this. Would be great, if you could give a code snippet as well.

Sunil Kumar

Comment only
31 Mar 2014 Joseph Kirk

Joseph Kirk (view profile)

@Tyler, my other version can:

Comment only
30 Mar 2014 Tyler

Tyler (view profile)

Can this program find the shortest path from a distance matrix?

Comment only
03 Feb 2014 Surender moode

i will not understand this please explain me

Comment only
12 Sep 2012 Andrea

Andrea (view profile)

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.

Comment only
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

Comment only
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...

Comment only
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.

09 Jan 2007

Combined script and function into a single m-file that can be run "as is" or with user specified inputs.

Contact us