File Exchange

image thumbnail

Dijkstra Algorithm

version 1.0.0.0 (2.57 KB) by Dimas Aryo
Dijstra algorithm to solve shortest path problem.

113 Downloads

Updated 11 Apr 2012

View License

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]

Cite As

Dimas Aryo (2021). Dijkstra Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/36140-dijkstra-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (50)

淼 程

Rizki Ramadhan

ofir hadad

does the algorithm assumes directed graph?

Elena Floris

Hi, I tried this function with a matrix (16289X16289) that represent the values of the edge, specifically the distance between the edges, this values not are integer. I tried many example and the results of the function it is wrong. I don't understand what is the problem. Can you help me?

Chokri Khalfet

hi
i wanted to check your algorithm for stability, in a net of 3^7 possible combination has only failed in one.
the net is set up here (w is symmetric).
https://graphonline.ru/en/?graph=otGZuBAJBCVGNmhT
w=[ 0, 1, 0, 1, 0, 0, 0, 0, 0
1, 0, 1, 0, 1, 0, 0, 0, 0
0, 1, 0, 0, 0, 1, 0, 0, 0
1, 0, 0, 0, 1, 0, 1, 0, 0
0, 1, 0, 1, 0, 1, 0, 1, 0
0, 0, 1, 0, 1, 0, 0, 0, 1
0, 0, 0, 1, 0, 0, 0, 1, 0
0, 0, 0, 0, 1, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 1, 0];
[~,p]=dijkstra(w,3,7)
p =

7 4 3 2 3
p is impossible

Nardus

Thanks for your contribution. It it of great help. Congratulations.

Igor Sowa

sibabalo noludwwe

hi
i tried using the code and below is the error
Error using graph/subsref (line 7)
Indexing not supported.

Error in setupgraph (line 6)
if G(i,j)==0

Error in dijkstra (line 27)
A = setupgraph(A,inf,1);

Error in dijskra (line 23)
[cost rute]=dijkstra(G,13,2);

wang yanik

wang yanik

有中文交流一下的么?

Shaaib Naji

great code
can i use it to perfume bellman ford algorithm ?
what changes i have to make to accomplish that

Harry Mitchell

Good job!

Does this work for nodes where the edge weight is different depending on the direction that is taken?

matteo bartoloni

big Albert i love you!!!!

Mendi

peijin wu

ZHIHONG NG

Hi,
When i try to test run the program, it says Dijkstra algorithm requires more input arguments to run. :(

Zelong Shao

very good work,Thank you.

Caio Bastos

yang Li

Albert Carfax --> Thanks for your advice and it solve the problem (passing node 1).

Rofi SR

aqsa khan

Hi,
I am currently using this code in my research and it works perfectly fine for the small matrix but when i used this code to find the shortest path in large network which contains 3-4 lac nodes, Matlab gives me error of out of memory to create such a big matrix G. Please help me if you have any solution to this problem. Thanks

GIST

Albert Carfax --> Thank you!!

GIST

Kristian Takac

Hi,
Could you please tell me if it is possible to rewrite this algorithm to a form which will work with negative, respectively non-positive paths as well?

Thank you!

Miguel Ruiz

If dijkstra(G,1,2) = 3, how come dijkstra(G,2,1) = inf ?

Claire Wong

why it cannot define the A.
>> dijkstra(A, s, d)
Undefined function or variable 'A'.

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

flyingpig

Khang Nguyen

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

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.

MoysesDutra

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

David Molony

hanyu li

useful

Nikos Bousios

Palmer Anisi

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

Falk Lieder

Harry

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.

aqeel lami

aqeel lami

it works great and thanks

Ronan

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?

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 :(

Paul yang

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

Martin

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

Cosy

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. :(

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?

Alex George

any idea on how this works?

taewoo

!!

Poonam

good algo..

Matthias

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

MATLAB Release Compatibility
Created with R14SP1
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!