This algorithm is to solve shortest path problem.
[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.
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]
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
Albert Carfax --> Thank you!!
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?
If dijkstra(G,1,2) = 3, how come dijkstra(G,2,1) = inf ?
why it cannot define the A.
>> dijkstra(A, s, d)
Undefined function or variable 'A'.
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:
L = [L 1];
In listdijkstra, line 6, instead of having L=[L s], replace it with L=[s L]. That should solve the problem.
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.
Works perfectly in our problem.
Thanks a lot.
There is a bug in this code. Node 1 is usually replaced by node 4 for paths containing node 1
I recently find a bug of this code. If the path contain node 1, it generally will be replaced by the source node number.
it works great and thanks
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?
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 :(
it works great! is there a version that provides all paths, rather than just the shortest path?
does anyone have the comments for this code. It works perfectly but i would like to understand the role of each function
what is wrong with this example:
G = [ 0 1 2;
1 0 0;
2 0 0 ]
result: [3 2 2]
Can you help me?
PS: I see that Gautam Marwaha had the same problem. :(
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?
any idea on how this works?
It worked for my purpose! Thanks for it. 4 of 5 because i haven't tested it in extreme situations. Very well!!!
Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.