View License

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

» Watch video

Highlights from
Dijkstra Algorithm

4.45455
4.5 | 12 ratings Rate this file 176 Downloads (last 30 days) File Size: 2.57 KB File ID: #36140 Version: 1.0

Dijkstra Algorithm

by

Dimas Aryo (view profile)

 

Dijstra algorithm to solve shortest path problem.

| Watch this File

File Information
Description

This algorithm is to solve shortest path problem.

Usage
[cost rute] = dijkstra(graph, source, destination)

note : graph is matrix that represent the value of the edge. if node not connected with other node, value of the edge is 0.

example:
Finding shortest path form node 1 to node 7.

>> G = [0 3 9 0 0 0 0;
     0 0 0 7 1 0 0;
     0 2 0 7 0 0 0;
     0 0 0 0 0 2 8;
     0 0 4 5 0 9 0;
     0 0 0 0 0 0 4;
     0 0 0 0 0 0 0;
     ];
>> [cost rute] = dijkstra(G,1,7)

it will resulting

cost = 15
rute = [7 6 4 5 2 1]

Required Products MATLAB
MATLAB release MATLAB 7.0.1 (R14SP1)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (24)
13 Jan 2017 Albert Carfax

I found the error. To summarize what I've read of previous comments and confirmed myself, the code returns an incorrect route whenever the path passes through node one. This is because the code reorders the graph so that the source is node 1 and what was previously node 1 is now given the index that the source had previously (line 31: A=exchangenode(A,1,s);). When outputting the route, however, the indecies are not switched back properly. The index of the source is switched back (line 6 of linedijkstra: L=[L s];), but not the node was in the node 1 slot and got bumped out. Thus the route, if it passes through the original node one, will look like it passes through the source node and then still ends up at the source node.

You can fix the problem by either always arranging your graph so that the the source is node 1 or make the following substitution in listdijkstra.m:

Old code:

L=[L W(index2,1)];

New code:

if W(index2,1)==s
L = [L 1];
else
L=[L W(index2,1)];
end

Comment only
13 Jan 2017 flyingpig

09 Dec 2016 Khang Nguyen

In listdijkstra, line 6, instead of having L=[L s], replace it with L=[s L]. That should solve the problem.

Comment only
15 Nov 2016 MoysesDutra

This code have one problem when route pass on first node (node number 1)
I'm Still looking for this mistake on code to correct it.

Comment only
14 Nov 2016 MoysesDutra

Very good.
Works perfectly in our problem.
Thanks a lot.

30 Sep 2016 David Molony

16 Sep 2016 hanyu li

useful

Comment only
26 May 2016 Nikos Bousios

17 May 2016 Palmer Anisi

There is a bug in this code. Node 1 is usually replaced by node 4 for paths containing node 1

06 Jan 2016 Falk Lieder

24 Nov 2015 Harry

Harry (view profile)

11 Nov 2015 Shunbo Lei

I recently find a bug of this code. If the path contain node 1, it generally will be replaced by the source node number.

Comment only
13 Oct 2015 aqeel lami

13 Oct 2015 aqeel lami

it works great and thanks

Comment only
07 Sep 2015 Ronan

Ronan (view profile)

Could you please explain how you are defining nodes. It is not clear at all what how the source node and destination node are chosen and how the route relates to the start and end node?

Comment only
02 Sep 2015 Sara Baldwin

Hello I tried using this function but I am having trouble....In my matrix I have whole numbers but the matrix is a double (not sure why) and this algorithm is not working :(

Comment only
27 Feb 2015 Paul yang

it works great! is there a version that provides all paths, rather than just the shortest path?

26 Jan 2015 Martin

Martin (view profile)

does anyone have the comments for this code. It works perfectly but i would like to understand the role of each function

04 Dec 2014 Cosy

Cosy (view profile)

Hi there,

what is wrong with this example:

G = [ 0 1 2;
1 0 0;
2 0 0 ]

dijkstra(G,2,3);

result: [3 2 2]

Can you help me?

PS: I see that Gautam Marwaha had the same problem. :(

Comment only
16 Dec 2013 Gautam Marwaha

This code mostly works fine but fails for a few cases:
G = [0 1 1 1 1 0 0;
1 0 0 1 0 1 0;
1 0 0 1 0 1 1;
1 1 1 0 1 0 0;
1 0 0 1 0 0 1;
0 1 1 0 0 0 1;
0 0 1 0 1 1 0];

dijkstra(G,3,5) yields [5 3 3] or [3 3 5]. Any ideas why this happens?

Comment only
09 Dec 2013 Alex George

any idea on how this works?

Comment only
24 Nov 2013 taewoo

taewoo (view profile)

!!

25 Apr 2013 Poonam

Poonam (view profile)

good algo..

Comment only
25 Mar 2013 Matthias

It worked for my purpose! Thanks for it. 4 of 5 because i haven't tested it in extreme situations. Very well!!!

Contact us