Graph Theory: Dijkstra's Algorithm

[@numidianarchers195]

Dijkstra's takes a bit to comprehend but I found it useful to keep in mind your introductory declaration that the aim of Dijkstra's Algo'm is to find the shortest path between two vertices. This implies that every path's distance is calculated and compared. Remembering this helped me understand this video (which I so happened to view several times).

[@spleen387]

I noticed you didn't keep track of the vertexes/path that you took to each node to give it its score. that makes it a little unclear as to why you traced the path that you did in the end

[@aaronsmarrella3239]

Going backwards from A to G, you look at where the current vertex weight was, since a few vertices had the numbers marked out, that means that that edge is no longer the shortest path. For example, when he went from A, he did not go from A to C because that gave a value of 15, where 13 is less- So B is next, then from B he did not go from B to E because its value was marked as 13 and the lowest was 12-so D. From D the lowest value was 9 not 10 so he went from D to E, not F because D to F was 10, and lastly from E he went to G because it had a value of 7. Again, he did not go from D to F to G because that gave a value of 4 + 6 or 10. and 10 is higher than the value of 9 given to D. So he simply went back the path that gave the lowest number. He didn't keep track of the vertices/path as he was going because it could easily be changed as he went on depending on which edge gave the lower value. He would have to keep on marking it then removing it. It gets easier to follow the final path by looking at the numbers on the vertices and which numbers got marked out so you don't go down the wrong path. I hope that makes sense

[@spleen387]

@Hortensia Wolfing it's a scam lol dont fall for it

[@monoman4083]

marking not clear for route back at b+d

[@fauzytech]

should we do trackback in the end?

[@89coolsush]

Very clear and to the point. Good work.

[@senthilkumarb2761]

way of explanation is fantastic

[@Mathispower4u]

Thank you for the comment.

[@nunosm9106]

Best tutorial on youtube

[@Mathispower4u]

+Nuno SM Thank you for the comment and for watching.

[@syedmasroorhussain]

How did you calculate the last shortest path? The one which is labelled 13? I'm confused because you used all the vertices and chose a different path containing less vertices than the total amount of vertices

[@chelseygiot8390]

Hi, in graph data structure, if average path length is 2π and a longest geodesic of ≥ 6π, how to draw node- link diagram ?

[@isabelelsneralmonte5512]

Hey, what if i have a much large number of vertex? is there a way to do it faster?

[@jonathanorozco5689]

Such a good video. THANK YOU.

[@MujeebulHasan]

How do you find shortest Path is ABDEG ...

[@SlavqBeats]

Mujeebul Hasan Yeah, I'm wondering the same thing...

[@Imfors4ken]

Hi.. I had the same question at first but then I came with a solution ... just add a name of the vertex, which was the starting point for the shortest value (path). So 13-B, 12-D, 9-E, 7-G. What do you guys think ?

[@SlavqBeats]

I've implemented it and it works when i do something like this: Start from starting vertex (A in this case) and go to neighbor vertex with less edge weight + vertex distance. So in this case, we don't go to C, because 4+11 > 1+12. So we go to B. Then we go to D, because 3+9 (D) is less than 6+7 (E). Then, from D we go to E because 2+7 (E) is less than 4+6 (F) and less than 2+11 (C). And so on, until we reach destination vertex G.

[@lucyjenny1987]

Mujeebul Hasan we have an extra tag for parent node at each node. when a node's distance gets updated because of a previously visited node, its parent node gets updated. for eg, in the above example, when D's distance changed from 10 to 9, its parent change from F to E.

[@spleen387]

+Lucy Jenny that's how its supposed to be done XD

[@sudipsah9395]

but you have visited vetex F also and you have marked it

[@mohammadrostami6125]

You made my day.

[@sensei0101]

Briliant, just briliant

[@amateurbeginner7538]

It not that some people has some will power and some dont , it is that some people are ready to change and others are not :) :)

[@vikasraj9497]

why shortest path from only a,b,d,e,g.why not a,b,e,g or a,e,f,g.

[@slowdown_]

+Vicky Torronto first: a,e,f,g is not possible. second a,b,e,g is 14 so its not the shortest ? if u cant simple math then u are wrong here...

[@mastimaro770]

thank you very much sir!!

[@football24hd1]

thank you it was very helpful

[@shoshoar6414]

thank U ^_____^ it's such a good video :))

[@ritikanegi1604]

Thank you so much

[@lateshpatil9262]

ty man...

[@vijayaganeshselvakumar1534]

thanks

[@qa1030]

thanx now i understood ^^