thank you! My Uni professor just explained this in such a complicated way.. and you do it within 10 minutes in such an easy way! you are the best, I love you.
This is the best explanation for Dijkstra's that I have seen on the net. I was having a hard time with this algorithm until I saw it explained like this. It helped me finish my project. Perfect!
OMG that was amazing i was desperate to understand this thing cause there are only 4 hours till my final and then i found this tutorial when i was revising thnq so much you saved me
Thanks a Lot !! I have Exam tomorrow too !! This algorithm has been a headache to me for a long time untill I saw and understood your very good leçon a few seconds ago ! Thanks again Sir !
Yes! Finally someone made a Witcher reference. I was browsing xkcd and suddenly "Dijkstra's algorithm" came out of nowhere. I was like "What sorcery is this??"
Now to find other paths, for example, as you said, D to H or H to G, you use the same method that the instructor used in this video. Notice that the instructor started with A - this was his starting vertex. To find a path from a vertex other than A, simply use the same method starting with that vertex instead (for your problems, D or H respectively) Hope all of this helped! :)
wow, now if math teachers could find ways to be this straightforward and concise in their teaching, we'd all be astrophysicists by now. Nice explanation
This one was very helpful. The other video I watched gave me the impression we chose the new vertex from the list of unvisited adjacent vertices because the graphs were too simple. This one was complex enough (having h have only one path leading in) that it made it clear we are choosing the next vertex to check just from the list of unvisited vertices. Thank you.
I love your explanation about algorithm. what is your youtube channel ?. your explanation on BFS and DFS destroyed my 15 year old fear about Graph problems. you explain things 1000 better than a Professor of MIT. Thank you !!!
B:20, C:40, D:50, E:N/A, F:30, G:70, H:60. For clarity, ignore the "small letters" under the numeric line values; they represet the "via node". Each line value from left to right aligns with each Goal Node's "main column", starting with B (focus on the letters written in blue at the top). That stated, to get the shortest path from A to Goal n: read *only* the numerical values on the final line (#7). (first value is for B .. last value is for H).
You take a look at the values in row 7: G can be reached the fastest via D (as D is the last vertex mentioned in column G) D is reached via C, C via F, F via B, and B via A. So to reach G by the shortest path, you go A->B->F->C->D->G
The TSP is the hardest problem to solve, as it is an equivalent problem to all of the other hardest problems (the rest of those that are NP-complete)--what you are describing is a probabilistic approach which will estimate (but can't guarantee) an optimal path, which one could argue isn't a solution as the problem is to find the optimal path which you may or may not have done with this.
This is an outstanding video. The only example or scenario that seems to be missing is how to manage/make a decision when you have two (2) edges from the same node (so two different path options from the same node) that cost the same...e.g. going from F to C or from F to D and they both cost 40.
Note I'm just a student practising this, so I'm not sure if it's correct but seems to have worked and made sense, at least for me so far. But still take it with a massive grain of salt, and if somebody could correct me that'd be great choose either one, just make sure it's the shortest one or among the shortest routes as calculating using shortest routes is the whole point of the algorithm. Also if to a certain node you have got 2 paths of the same length, just write something like 60, (A, D) down into the table. For example, if both A and D lead to E at a cost of 60 each, write 60, (A, D) under E. Then you can pick either one, the point is just to cover all the nodes.
Thank you very very much. You explained it well and I understood it well. My teacher didn't haven't taught us this (as far as I remember), but gave us an assignment which we have to use this method to solve (it said so in the problem, as in we have to specifically use this method). So I'm really really thankfull for this video. Once again, thank you.
You usually use a secondary criterion for selection. In our class we select according to alphabetical order. For example, if A -> C = 20 & A -> G = 20, we select C as it comes first in the alphabetical order.
to get a best path, take for e.g. the best path from A to D (obtained with Dijkstra's alg), you follow the reverse path given by the parents from which they were explored. So starting from D, you see that it was visited from parent C and has a cost of 50. Now going to C, you see that its parent is F. And F was visited through B (its parent). And finally, B's parent is A. So the path would be A-B-F-C-D. The idea is that you have to reconstruct your path from _goal_ node to the _starting_ node.
@elgonost You could choose a random path, or the path given by the algoritm checking for the lowest number. I suspect you could enhance the algoritm to track both paths in that case. Now it only finds the shortest path to a point, if you rewrite the algoritm to track both and continue further steps seperatly, you'd get an algoritm that gives all shortest paths to all points.
You need to start working on this algorithm with the starting point in mind. In this case, he used A as a starting point. The values at the are the shortest paths from A to any other vertex.
Take path from A to G, for example. Start from G: you've written down before that the lowest-cost path approaches G from D. So you now take D and look where the best path leads from. Then it's just recursion all the way back to A, and you just went the best way from A to G (in opposite direction). But I guess you've figured it out after 6 months :-)
Very good tutorial, it be even better if you talk about how using a min priority queue is improvement over original algorithm Dijkstra submitted in his paper
@manojsam79 You only need the last row. Begin at the vertex you're interested in, look up its parent (the node that's written under the optimal cost), than look up the parent's parent etc. Proceed until you reach the starting node. Reverse the list of nodes to get the shortest path. E. g. the shortest path to H is H, C, F, B, A reversed, that is A, B, F, C, H
Thanks, this helped me. I have to specify that this is no the Djikstra original algorithm: this is implemented choosing the min vertex (with a min heap), the original algorithm choses the first node of a queue. Anyway, it does not change the core buisness :) Thanks!
This is a completely different problem to what you describe (TSP). Dijkstra's algorithm finds a 'single source shortest path', and so it computes the shortest path from A to any other vertex. It doesn't require that all (or any) of the other points be included in the solution's path.
What I've concluded is that I need to keep applying Dijkstra's algorithm until my destination node is marked as permanent. Then I can stop and I don't need to visit the rest of the nodes. This makes the algorithm a little more efficient.
Excellent explanation, I just passed an exam because of this video, god bless you!
Short and easy to understand. Great job.
Hate books that spend pages over pages that make you want to burn it all.
thank you! My Uni professor just explained this in such a complicated way.. and you do it within 10 minutes in such an easy way! you are the best, I love you.
you explained 1 semester in 10 minutes
what school and what year ?? wtf
30 minutes of my Data Structures and Algorithms lectures. I think you belongs to mid of 20th Century
fuck your school then
We just explained that for 30 minutes,elps...
is it so?? advanced?
we are studying this in our 3rd sem and it comes of only 8-10 marks...it's an average level of problem.
This is the best explanation for Dijkstra's that I have seen on the net. I was having a hard time with this algorithm until I saw it explained like this. It helped me finish my project. Perfect!
that's how you squeeze an hour of course into 10 mins
Very well explained. Explaining complex things so easy is really an art. You are an artist. Thank you and Good wishes to you.
Thanks alot man
I passed my exam last year because of this video , thanks from egypt .
Explained much better than my lecturer! Thanks!
OMG that was amazing
i was desperate to understand this thing cause there are only 4 hours till my final and then i found this tutorial when i was revising
thnq so much you saved me
These have been really good for revising for my Data Structures and Algorithms exam today! thank you :)
Thanks a Lot !! I have Exam tomorrow too !! This algorithm has been a headache to me for a long time untill I saw and understood your very good leçon a few seconds ago ! Thanks again Sir !
You just saved me for my final exam! This is the only problem I had trouble with. Thank you!
This video is more than 10 years old, yet still so useful. Going into exams with more confidence after watching your explanation, thank you!
I'' be sitting for Data Structure final exam paper in 3 days time..
You just saved my life!!~
:) :)
Excellent!!! you made it really easy to grasp in 10 minutes than a full class lecture. Thank you very much, keep up the good work.
Amazing man , really thank you, I have a final exam tomorrow and your video and easy explaining was too helpful for me , Keep on
fantastic one. i had been trying to understand this for a long time but this video really took very few of my time to make me understand
Very nice, I think you saved my mark for this semester.
Cheers from Russia
I like it! I'm going to pay him a visit in the Bath House, in Novigrad, I believe congratulations are in order!
Yes! Finally someone made a Witcher reference. I was browsing xkcd and suddenly "Dijkstra's algorithm" came out of nowhere. I was like "What sorcery is this??"
Vojtěch Janků Ahaha 😂😂
Now to find other paths, for example, as you said, D to H or H to G, you use the same method that the instructor used in this video. Notice that the instructor started with A - this was his starting vertex. To find a path from a vertex other than A, simply use the same method starting with that vertex instead (for your problems, D or H respectively) Hope all of this helped! :)
wow, now if math teachers could find ways to be this straightforward and concise in their teaching, we'd all be astrophysicists by now. Nice explanation
helped a lot, managed to learn more in 10 minutes with your explanation, than with my prof's lecture that took 3 hours
I have an exam tomorrow and you have just saved my life! Thanks!
This one was very helpful. The other video I watched gave me the impression we chose the new vertex from the list of unvisited adjacent vertices because the graphs were too simple. This one was complex enough (having h have only one path leading in) that it made it clear we are choosing the next vertex to check just from the list of unvisited vertices. Thank you.
God Bless u made it as simple as a childs game!!! Thanks to you,I can now score well.Thanks a lot man!!!!! keep posting!
Really helped, man !! I watched this video an hour before my exam, went there and nailed it !!! :D
Can you believe this is a 5 year old video? Good work mate
kkkkkk
Now it's 10 year old 😱
Can you believe that your comment is 4 years old?
Hiii
its 11 years now lool
wow i have been searchin through my skripts and through wiki to learn that stuff. but that was the best explanation by far! good job and thank you!
I love your explanation about algorithm. what is your youtube channel ?. your explanation on BFS and DFS destroyed my 15 year old fear about Graph problems.
you explain things 1000 better than a Professor of MIT. Thank you !!!
+Mubeen Ali pretty sure he was watching open courseware and was confused by a university presentation that explains theory as well...
I mean I thought the MIT lecture guy explained it pretty well..
Thank you soo much i had finals 3 hrs later, i just needed to und this part and im done, Thanks to you u saved hours of mine. Keep it up!
You rule! you are the only exapmple like this put there! and Ive been looking for like 2 hours. Thank you :)
I don't leave comments, but I had to say a job well done with this explanation. Just perfect!!
This algorithm is so annoying, thank you for making it more clear than the textbook.
Soo simple and easy way of exaplaining. Hats OFFF
This must be one of the only 16:10 vids on TH-cam :D Thanks for a great explanation btw
Thanks for this clear illustration and explanation. Good Job.
Thank you so much, this was fantastic for clarification. Watched two of your videos so far and they've been very well done.
Best Explained I've ever seen.
B:20, C:40, D:50, E:N/A, F:30, G:70, H:60. For clarity, ignore the "small letters" under the numeric line values; they represet the "via node". Each line value from left to right aligns with each Goal Node's "main column", starting with B (focus on the letters written in blue at the top). That stated, to get the shortest path from A to Goal n: read *only* the numerical values on the final line (#7). (first value is for B .. last value is for H).
So well explained that my Grandma understood it!
An awesome explanation with a great example. You have covered all of the possible trickiest cases. Thanks a lot :)
Just wanted to thank you profusely. And also to say this is my first actual youtube comment. Hello world!
Awesome, Exam later today and was totally blanking on Dijkstra algorithm
Thanks heaps
Understand it without any difficulty.Thanks man.
You take a look at the values in row 7:
G can be reached the fastest via D (as D is the last vertex mentioned in column G)
D is reached via C, C via F, F via B, and B via A.
So to reach G by the shortest path, you go A->B->F->C->D->G
Best explanation so far, Great Work !!
This is the 3rd algorithm you've taught me!
The TSP is the hardest problem to solve, as it is an equivalent problem to all of the other hardest problems (the rest of those that are NP-complete)--what you are describing is a probabilistic approach which will estimate (but can't guarantee) an optimal path, which one could argue isn't a solution as the problem is to find the optimal path which you may or may not have done with this.
Dude. Thank you so much. This helps me a LOT, I have a final tomorrow!
Wtf. Didn't know it could be explained so easily. Thanks!
This is an outstanding video. The only example or scenario that seems to be missing is how to manage/make a decision when you have two (2) edges from the same node (so two different path options from the same node) that cost the same...e.g. going from F to C or from F to D and they both cost 40.
Note I'm just a student practising this, so I'm not sure if it's correct but seems to have worked and made sense, at least for me so far. But still take it with a massive grain of salt, and if somebody could correct me that'd be great
choose either one, just make sure it's the shortest one or among the shortest routes as calculating using shortest routes is the whole point of the algorithm. Also if to a certain node you have got 2 paths of the same length, just write something like 60, (A, D) down into the table. For example, if both A and D lead to E at a cost of 60 each, write 60, (A, D) under E. Then you can pick either one, the point is just to cover all the nodes.
Heh, you're much better than my professors at explaining stuff. Would have thrown a like your way...
Thank you so much. My textbook is super vague on this, and now I finally understand.
Thank you very very much. You explained it well and I understood it well. My teacher didn't haven't taught us this (as far as I remember), but gave us an assignment which we have to use this method to solve (it said so in the problem, as in we have to specifically use this method). So I'm really really thankfull for this video. Once again, thank you.
You usually use a secondary criterion for selection. In our class we select according to alphabetical order. For example, if A -> C = 20 & A -> G = 20, we select C as it comes first in the alphabetical order.
Thanks a lot, this will help me with my test next Tuesday. :)
Best dijktra demo. evar
to get a best path, take for e.g. the best path from A to D (obtained with Dijkstra's alg), you follow the reverse path given by the parents from which they were explored. So starting from D, you see that it was visited from parent C and has a cost of 50. Now going to C, you see that its parent is F. And F was visited through B (its parent). And finally, B's parent is A. So the path would be A-B-F-C-D. The idea is that you have to reconstruct your path from _goal_ node to the _starting_ node.
nice man ! i was trying to understand what " vertex relaxation " was and i got it from your video
Incredibly helpful video - completely ironed out my confusion with this topic! Thank you! :D
@elgonost You could choose a random path, or the path given by the algoritm checking for the lowest number. I suspect you could enhance the algoritm to track both paths in that case. Now it only finds the shortest path to a point, if you rewrite the algoritm to track both and continue further steps seperatly, you'd get an algoritm that gives all shortest paths to all points.
This is absolutely brilliant. Just what I needed! Thanks!
I'm glad I found this video. I'm working on a project for class that requires this algorithm.
Thanks a lot for posting this, it makes perfect sense now
thank you very much amigo, your time and effort is greaty appreciated
Thanks so much, It's helping me for my test tomorrow.
me too
thnk u so mch... have xams in 8 hours :P
.
thnx 2 u... will at least score 5 marks for Dijkstra algo :D
Very nice! -- quick question: how did you create the video? Love the hand-written style! Looks like NoteShelf on the iPad.
Once we are in the final situation (9:01), how can i deduce the shortest path between 2 random vertices ???
You need to start working on this algorithm with the starting point in mind. In this case, he used A as a starting point. The values at the are the shortest paths from A to any other vertex.
Take path from A to G, for example. Start from G: you've written down before that the lowest-cost path approaches G from D. So you now take D and look where the best path leads from. Then it's just recursion all the way back to A, and you just went the best way from A to G (in opposite direction). But I guess you've figured it out after 6 months :-)
Very good tutorial, it be even better if you talk about how using a min priority queue is improvement over original algorithm Dijkstra submitted in his paper
@manojsam79 You only need the last row. Begin at the vertex you're interested in, look up its parent (the node that's written under the optimal cost), than look up the parent's parent etc. Proceed until you reach the starting node. Reverse the list of nodes to get the shortest path.
E. g. the shortest path to H is
H, C, F, B, A
reversed, that is
A, B, F, C, H
Really well explained! And easy to remember. Text books should teach this way of doing it, much more pedagogical.
Thank you -- awesome explanation! I'm needing to implement the algorithm, and this helps tremendously!
this video helped me in my final exam.... THANKS A LOT !!!!!!!
Thanks, this helped me. I have to specify that this is no the Djikstra original algorithm: this is implemented choosing the min vertex (with a min heap), the original algorithm choses the first node of a queue. Anyway, it does not change the core buisness :) Thanks!
a quite nice visual explanation, good stuff
Thank you soo much, by far the best explanation ive found :-)
Well done, excellent description. But why no rating?
That was a really good video, thank you so much I found this really confusing in the beginning but this really helped :)
Thanks! 🔝 10 years later 🌱
awesome explanation..very clear..hoping for more uploads.. :)
You're using a tablet? Or are just that good with the mouse? Great video! :) I'm planning myself something interesting in the field...
Thi vid makes it very easy to understand the algorithm.
Thanks a lot =)
finally the video for directed weighted Dijkstra graph.
awsome I have understood Everything...............
Very Nice Vedio Thanks..
This is a completely different problem to what you describe (TSP). Dijkstra's algorithm finds a 'single source shortest path', and so it computes the shortest path from A to any other vertex. It doesn't require that all (or any) of the other points be included in the solution's path.
A very good explanation, very helpful for my exam!
Thank you. You explained pretty easy to understand.
What I've concluded is that I need to keep applying Dijkstra's algorithm until my destination node is marked as permanent. Then I can stop and I don't need to visit the rest of the nodes. This makes the algorithm a little more efficient.
I really like this notation. Thank you!
thanks a lot... it realy helped me understand how the algo works
Really great video! Very simple and clear, and now I understand :D
Thank you. It was easier than I thought!!! :) And you explained everything perfect, indeed :)
That's been GREAT help! Thanks :))
Great explanation!
Thank you for posting.
Thank you so much for this video! So helpful!
This helped soo much. Thanks for posting this video.
What did you use to draw on? I've been looking for some sort of pdf theme that I can doodle my notes on. Great video by the way!
This is much better than my text book explanation