How to find least-cost paths in a graph using Dijkstra's Algorithm. This video is distributed under the Creative Commons Attribution 2.5 Canada License. creativecommons...
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!
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??"
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 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.
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 !
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! :)
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).
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.
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
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.
@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
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.
Going from Vertex B to F without processing other neighbors of A is a digression from BFS approach. More often Dijkstra is considered BFS with greedy approach.
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.
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
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!
@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.
The shortest path, of all in the return set, is A->B=20. But that's not the intent nor the answer for this problem. The algorithm returns a *set* of shortest paths (B-H), given a topology of nodes with multiple connections (or edges). Not just a single, shortest path.
Only gor the sake of a clarification; the "traveling salesman" problem you describe is not the hardest problem to solve. It's just somewhat hard if you want to brute force all paths (which is silly), but even that is not too hard by moderns standards (You can brute-force it in a GPU with CUDA now a days!) You can "solve" it cheaply by using genetic algorithms. Look it up :) Also, it's been thaught for too much time in universities by teachers who don't like to keep up-to-date.
we can take either of the paths that u might get while executing the algorithm..because u need to find the least cost and u will get equal costs from both least cost paths...we need the method which we will get
you name the nodes to have some reference, it's up to you but usually it is easier to read/understand if you follow a given order such as alphabetic... at least for the starting point as for the final result the logic is shorter path and not names
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 :-)
In case there are 2 paths with the same minimum cost which node will we choose as next? For example. Lets say there is a path from A to E that costs 20. We have A->B costing 20 and A->E costing 20. Which one will we choose??
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.
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.
that's how you squeeze an hour of course into 10 mins
Thanks alot man
I passed my exam last year because of this video , thanks from egypt .
Very well explained. Explaining complex things so easy is really an art. You are an artist. Thank you and Good wishes to you.
Explained much better than my lecturer! Thanks!
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!
This video is more than 10 years old, yet still so useful. Going into exams with more confidence after watching your explanation, thank you!
Amazing man , really thank you, I have a final exam tomorrow and your video and easy explaining was too helpful for me , Keep on
These have been really good for revising for my Data Structures and Algorithms exam today! thank you :)
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
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 😂😂
This algorithm is so annoying, thank you for making it more clear than the textbook.
I'' be sitting for Data Structure final exam paper in 3 days time..
You just saved my life!!~
:) :)
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
You just saved me for my final exam! This is the only problem I had trouble with. Thank you!
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.
Very nice, I think you saved my mark for this semester.
Cheers from Russia
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 !
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! :)
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..
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).
I don't leave comments, but I had to say a job well done with this explanation. Just perfect!!
I have an exam tomorrow and you have just saved my life! Thanks!
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.
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
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.
Soo simple and easy way of exaplaining. Hats OFFF
I'm glad I found this video. I'm working on a project for class that requires this algorithm.
Wtf. Didn't know it could be explained so easily. Thanks!
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.
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!
this video helped me in my final exam.... THANKS A LOT !!!!!!!
You rule! you are the only exapmple like this put there! and Ive been looking for like 2 hours. Thank you :)
Really well explained! And easy to remember. Text books should teach this way of doing it, much more pedagogical.
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!
This is the 3rd algorithm you've taught me!
An awesome explanation with a great example. You have covered all of the possible trickiest cases. Thanks a lot :)
@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
Best Explained I've ever seen.
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.
Really helped, man !! I watched this video an hour before my exam, went there and nailed it !!! :D
finally the video for directed weighted Dijkstra graph.
Thanks! 🔝 10 years later 🌱
Thanks for this clear illustration and explanation. Good Job.
Awesome, Exam later today and was totally blanking on Dijkstra algorithm
Thanks heaps
nice man ! i was trying to understand what " vertex relaxation " was and i got it from your video
Best dijktra demo. evar
Whichever one you get to first is the one you use. They both are valid paths though, so you can technically use either one.
College final in 3 hours and 1/3 of it is going to be on this. I have not shown up to class once and now I am cramming. Pray for me.
Heh, you're much better than my professors at explaining stuff. Would have thrown a like your way...
Going from Vertex B to F without processing other neighbors of A is a digression from BFS approach. More often Dijkstra is considered BFS with greedy approach.
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!
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.
Thank you so much, this was fantastic for clarification. Watched two of your videos so far and they've been very well done.
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
Incredibly helpful video - completely ironed out my confusion with this topic! Thank you! :D
Watching this after like 9 years of it. Wow.
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!
good explanation thanks from Poland.
Thanks so much, It's helping me for my test tomorrow.
me too
This must be one of the only 16:10 vids on TH-cam :D Thanks for a great explanation btw
Thanks a lot for posting this, it makes perfect sense now
@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.
Thanks a lot, this will help me with my test next Tuesday. :)
a quite nice visual explanation, good stuff
Dude. Thank you so much. This helps me a LOT, I have a final tomorrow!
thnk u so mch... have xams in 8 hours :P
.
thnx 2 u... will at least score 5 marks for Dijkstra algo :D
I really like this notation. Thank you!
The shortest path, of all in the return set, is A->B=20. But that's not the intent nor the answer for this problem. The algorithm returns a *set* of shortest paths (B-H), given a topology of nodes with multiple connections (or edges). Not just a single, shortest path.
AWESOME !!!!! U SIR JUST SAVED A LIFE
Thank you soo much, by far the best explanation ive found :-)
Thi vid makes it very easy to understand the algorithm.
Thanks a lot =)
Only gor the sake of a clarification; the "traveling salesman" problem you describe is not the hardest problem to solve. It's just somewhat hard if you want to brute force all paths (which is silly), but even that is not too hard by moderns standards (You can brute-force it in a GPU with CUDA now a days!) You can "solve" it cheaply by using genetic algorithms. Look it up :) Also, it's been thaught for too much time in universities by teachers who don't like to keep up-to-date.
we can take either of the paths that u might get while executing the algorithm..because u need to find the least cost and u will get equal costs from both least cost paths...we need the method which we will get
You can choose the first or the one path you want to choose.
you name the nodes to have some reference, it's up to you but usually it is easier to read/understand if you follow a given order such as alphabetic... at least for the starting point as for the final result the logic is shorter path and not names
Thank You. Easy and Simple explanation.
Hi thanks for this videp.I am student from BITS.This one is too good
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 nice! -- quick question: how did you create the video? Love the hand-written style! Looks like NoteShelf on the iPad.
boy you are a real troubleshooter!
This is absolutely brilliant. Just what I needed! Thanks!
Thank you -- awesome explanation! I'm needing to implement the algorithm, and this helps tremendously!
@RWPCreations Leave the cost and through node as it is...It can also be changed if wanted
WONDERFUL really thanks
u save a hour from my life
u r awesome .. luv ur teaching u r always to da point .. tada
awsome I have understood Everything...............
Very Nice Vedio Thanks..
There is some agreed upon path to use. You might pick the letter least alphabetical.
That's been GREAT help! Thanks :))
Finally I understand that. Thanks a lot.
Excellent, clear n concise
Well done, excellent description. But why no rating?
A very good videos, I understand really now.
Thank you
awesome explanation..very clear..hoping for more uploads.. :)
In case there are 2 paths with the same minimum cost which node will we choose as next? For example. Lets say there is a path from A to E that costs 20. We have A->B costing 20 and A->E costing 20. Which one will we choose??
Thanks for the gr8 explanation. it was very helpful.
what happens when youre picking the smallest path to analyze next (that you havent done yet) and you get two paths of the distance?
So what's the shortest path here? We get this table done, and how're we suppose to identify the path now? From A to where through which vertices?