Dijkstra's Algorithm - Computerphile
ฝัง
- เผยแพร่เมื่อ 3 ม.ค. 2017
- Dijkstra's Algorithm finds the shortest path between two points. Dr Mike Pound explains how it works.
How Sat Nav Works: • Satellite Navigation -...
Slow Loris Attack: • Slow Loris Attack - Co...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
To understand recursion, one must first understand recursion.
Stack overflow.
Navaron No, his joke gave me a stack overflow.
WesOfX You need a base case.
Should have added some recursion limiting flag...
That's deep
You finished to early. There were still other nodes in the priority list that had a lower priority than 'E'.
So it was still possible to find a shorter way!
Djikstra's Algorithm terminates after the goal node has been processed, not when the first path has been found!
Yep! Thanks for pointing this out, I spotted it too late :) I should have expanded d and f. Had there been a path from say d to e that could have changed things.
Hey Mike, what is the name of the C++ book behind you? Do I see the Elements of Statistical Learning as well there?
Melvin Klein C++ he needs vitamin C more like. ...
If you're ever interested in getting back into it and want some less outdated material since C++ has been changing a lot in the last five years or so, I highly recommend Scott Meyer's 'Effective modern C++' (which presupposes a knowledge of older C++, however, but since you seemed to have that)! c:
If you're into videos, CppCon has uploaded a great number of them over the last few years about almost any C++ topic you could imagine too. They're really nice especially for the modern examples.
I think this type of video is exactly the level of complexity your channel should be at. Stuff around the first undergraduate year of a typical Computer Science student, well explained is understandable for the average viewer but also interesting enough for advanced viewers.
We did dijkstra's algorithm in our second year of uni, but it still is appropriate for year 1.
billy653 I did it in high school, as well as A*
Welcome to the Mike Pound fan club. Far and away the best presenter on this channel. There needs to be a Mike Pound playlist if there isn't one already.
ya most advanced user would have already done this as a part of their course , but still this was an interesting topi to cover and just so many peaple payed attention to the steps as they pointed out the possible mistakes
this is taught almost anyone in engineering or in a technical field or last year of high school , i was first taught this technique in maths
A
One big mistake that I think a lot of people have already noticed: you do not stop the algorithm the instant you find a path to the end. Instead, you just put the end node in the list and continue until you fully process the end note and put it in the discard. This is because the first path you find may not be the optimal one, especially when, as shown in the video, multiple partial paths exist with the same length so they could be processed in any order, so you need to keep working until you can be sure you’ve gotten all possible paths.
For example, take a simple square with four nodes like this, with paths along the four edges with lengths as such:
S-1-A
| |
2 4
| |
B-2-E
In order to find the shortest path S to E, Dijkstra’s algorithm would start with this:
S0 Ai Bi Ei
First step is to process S; it has paths of 1to A and 2 to B, creating this:
(S0) A1S B2S Ei
Next is to process A, which has only one open path, of 4 to E for 4+1=5:
(S0 A1S) B2S E5A
Now as you described it, the algorithm would end immediately, with the path of SAE of length 5. But in fact, this path is obviously not optimal. In the correct algorithm, one would process B next, which has a path of length 2 to E for a lesser total of 4:
(S0 A1S B2S) E4B
Now you would process E, which had nothing to do, and now the algorithm would end and return the true shortest path of SBE length 4.
Heck, your own video shows an example of why you need to do this. At the very start, you have a triangle with sides 7-3-2, and you note that the SA path of length 7 is left there until you process B, which gives you a shorter SBA math that overrides the other one. If E was at the other end of that 7 path instead of A, it would have returned immediately and ignored the shortcut!
Real Dijkstra's Algorithm implementations actually continue searching until the destination node E is at the top of the priority queue, as theoretically either from D or F there could be a path of weight < 1 to node E, leading to a shorter path than the found one of weight 7, in the situation at 8:31
Yea, it's possible that there is, for instance, a faster path from G to E that passes through another node.
A large number (most?) of practical implementations use integer weights disallowing 0 (which is equivalent to 2 nodes being the same node anyways). This allows a linear runtime complexity.
Daniel Smith that seems like a rare edge case to me. If G-E was 3 instead there could still be a shorter path.
Rare edge case for what in particular? Wanting a linear time guarantee with a simple solver? No, most paths are just ints because it's easier to deal with computatinoally and algorithmically.
As for if G-E was 3 yes, there could still have been a shorter path. Same as if you had a different graph. Thing is he already checked the length from G->E and was likely under the assumption all weights are integers (partially because they all are, partially because he references "the implementation he knows" in networking at the beginning which is likely integer limited for the reason I mentioned.
Yeah kind of annoying that they didn't show that and just stopped
Ah, Dijkstra. What a lovely name.
it just rolls of the tongue
It does if you're Dutch. You can imagine "ij" being similar to "y"
I know, I'm Dutch and my last name is Dijkstra. 😄
That does not make it better in English...........
Matthijn Dijkstra I imagined Dutch people chuckling in the background of this video.
Please do A-star next!
I'm pretty sure the end bit about the heuristics was leading into that, haha
smash mouth? 😂
It's exactly dikstras but you have a heuristic that estimates the distance to the goal at each node. You add this heuristic to path length and that now becomes the priority. It's very very similar.
And then they'll get to the really pervy stuff, like customizable contraction hierarchies...
No, not my knee!
-Dijkstra
Too much witcher detected
Pathfinding error.
Dee-kstra or Dy-kstra?
@@dogemaester If you want to be closer to the original pronunciation, it would be Dee-kstra. Dy-kstra sounds more "englishified".
Dr Mike Pound is consistently making the content I've been enjoying the most on this channel. I'd love to see more videos with him
Dr Mike Pound just rocks!
This is awesome. I really like that you can feel the friendliness and good vibes between Dr. Pound and whoever is shooting the video. The energy passes through. This may seem immaterial, but this helped me engage and absorb more.
I haven't enjoyed a presenter on computerphile this much since Tom Scott. A Dr. Mike Pound playlist should be a priority. He is excellent at explaining every topic I have watched so far. Thank you very much for the content guys.
Before watching this video, I've always found myself confused regarding Dijkstra's implementation. This might just be the simplest and the best video for understanding how Dijkstra's algorithm works. Thank you very much!
In always enjoy watching Mike explain things! Nice video!
I love how a guest has never looked into the camera on this channel
they're all introverts.
I have read and watched other stuff on this topic before, but I never felt like actually getting it. You know, when you understand something, but you still feel uncertain about whether you actually got it. Now I watched this and my mind is clear. I get it, it feels intuitive now. Thank you so so much!
Dr. Mike is my fav
Definition of Recursion in the dictionary: See "Recursion"
error - maximum recursion depth reached
if you google "recursion", it says "did you mean recursion?"
@@Zmunk19 you're right :-)
@@Zmunk19 wow, i tried this
Why use recursion when you can easily get away with loops and stack? In most cases recursion is more "expensive" than itteration.
I just wanted to express my gratitude for the amazing work Computerphile is doing! I'm just going through Dijkstra's algorithm in my Discrete Mathematics course in uni and my lecture is utterly rubbish. Thanks to Computerphile video, I grasped the idea very quickly!
This video was actually great, I perfectly understood how the algorithm works in a simple but nevertheless complex concept. One of the best explanations so far. Great video!
This guy is always wonderful to hear. Thanks, Dr. Mike :)
This is a great start for videos of such high calliber.
If something is deeply difficult should be precented like it is with all the difficulties that such topic has. This is what I call authenticity. If it is measure theory then everything should be explained in great detail WITHOUT ommiting difficulty.
This guy gets it right.
wait
why was the search terminated after we found 1st route to end point? isn't it possible that last segment is huge and it isn't the shortest way?
Cause he messed up :D
look at 8:20
The pile at the right is your priority queue. You only ever work at the top most element of this queue. The Q is ordered by distance.
The mistake they made is that the put "e" at the top of the Q. It should be below "f" tho. This means they would have had to check "d" and "f" first, then go and check "e". Checking "e" means you've finished the algorythm.
It shouldn't have been terminated. Normally the search gets terminated when the goal is in the top of the priority list.
They seem to have forgotten that.
Because you sorted the nodes you were checking by the cost of getting to that node. Meaning you know that any other paths that might exist will have a higher cost.
read my answer. they messed up.
From what I can see, the routes that went down the roads to the right were both sitting at a value of 9. Since we had already found a path to E that was 7 which is < 9, then the search is stopped for all routes that have a current value > 7.
In a larger implementation of this algorithm, after a route to the destination is found, then any routes that are currently being searched are discarded if the current value is greater than the best route, as they cannot be the correct answer. (Note: I might be getting this part confused with dynamic programming, but it seems to me that they are essentially the same thing based on this simple example).
My computer organization class will be discussing Dijkstra and priority queues soon, I feel like I just got an amazing head-start.
In that case you better know there's a mistake in the video. Dijkstra's algorithm doesn't terminate until the destination node is at the top of the queue. The way Mike did it here, he found *a* path but *not* necessarily the *shortest* path. If for example the edge between g and e had weight of 14 or more, the shortest path would lead through k, but he wouldn't have found it. In this case Mike did get the shortest path, but he couldn't know that for sure before processing d and f.
Ironically, Dijkstra's algorithm as originally published in 1959 did not use a priority queue, and was asymptotically less efficient (quadratic run time). It took 25 years until Fredman & Tarjan published an upgraded version of it, with priority queue and an average O(n log n) run time.
I got lost at S....
Spoken like a true satnav.....
Same
Are you proud of your lack of intelligence?
What a lovely explanation Dr. Mike!
I really wish this guy was a professor at my university when i was studying. very well explained and feels engaging.
Thanks for the wonderful explanation and the short bit about its downfalls!
Good job on the graphics. Made the video a lot clearer :)
I asked for the English translation of another Dijkstra's Algorithm lecture video, and this is what I found. The explanation is a whole lot better.
Witcher shoutout
great. would love to see more videos on different type of algorithms.
Just want to say thanks for the sweet explanation on this algorithm. Couldn't learn it at school lectures but you made it clear.
Just yesterday I wondered about the travelling salesman problem and path finding and now you upload this video
The last part was amazing that dijkstra approach first consider the path with low cost no matter if they get you farther from the destination. So this is one disadvantage and also worth to mention that Dijkstra doesn’t work with negative weights. Perhaps I should say it works sometimes but not always.
Merry AoC day 15, pathfinders!
Who else is dutch? Netherlands, represent! Dijkstra mah boii!
KabyAlkaris aiiiii
I had no idea he was saying Dijkstra until I saw the intro.
KabyAlkaris No one cares, go back to your shunting yard.
Dutchman here! So very proud of Dijkstra whenever he and his Algorithm come up.
That ending seems to be tease for an upcoming A* video! Looking forward to it.
I found this video because I heard the name Dijkstra mentioned in another one of this channel's videos and wondered if it was the same person that invented the Shortest Path Algorithm. So I looked for this video to find out. Glad to find out *was* is what I wanted to see. IIRC: Dijkstra invented the algorithm to show how an early model mainframe computer can be used to solve the shortest path (traveling salesman?) problem. Don't know how accurately I remember it, but It's cool to find out that it is probably one of the oldest computer algorithms ever invented.
Great upload, keep em' coming!
Game developer here, I'd consider Dijkstra's (perhaps more A* but Dijkstra's is perfectly sufficient for small graphs) to be one of the core algorithms that everyone should know. Please do a video on Prim's (or one of the other MST algorithms) as well, my favourite algorithm, after Quicksort of course. :D
You made a small mistake. The algorithm terminates once you pop the end node 'E' from the priority queue, because that's when you know that you've found the shortest path to that node. You shouldn't terminate as soon as you've found only one path to the goal.
The algorithm should terminate in this case because the cumulative cost for all the other paths were already higher than the current path. If you had negative costs, then I believe you should only terminate once 'E" is popped.
No, D and F were still on the queue with 6 and E had 7. The path was ultimately the right one, but you can't guarantee that unless you wait until actually popping the goal node. If D or F had a path cost
they were just trying to build a overview for the algorithm rather than a comprehensive explanation which i think they did
@@philipbotha6718 Dijkstra doesn't work for negative weights
Very nice lead in to A*'s heuristic at the end, but I wish you'd called it out specifically there so the interested could go out and learn the next step themselves. (though you did mention it in the video which is good)
OMG i love this guy,i love this channel i missed my lecture where the Dr explained it and by all means i don't think he could've explained it better thanks
Thank you for this! Made it so simple to understand this algorithm!
I feel like pathfinding algorithms make less sense the more explanations I watch of them. T_T
I feel you T-T
T-T
T_T
very informative , it was like the movie finished in between , it would be lovely to check the second part for the limitations of Dijkstra's Algorithm
I was born in the US and my last name is Dijkstra. I majored in computer science before I ended up having to drop out. A few of my professors got excited when taking roll-call, and I had to explain to them that Dijkstra is like the “Smith” of the Netherlands from what I’ve been told. I think I might be related to him though! Just because I’m always trying to figure out the easiest way out of every situation
This is brilliant for Decision 1 revision for Further Maths!
Dijkstra, as I learned it, always searches the whole graph. What you presented is what I would call "A* with heuristic 0" (as you hinted in the final section).
By searching the whole graph with the, lets call it "complete" Dijkstra, you are actually computing the shortest path to all vertices in that graph. If you start searching at your destination instead of your starting point, you get a data structure that contains the shortest paths from all vertices to your desired destination (assuming you reverse the path(s) from the result). Applied in a routing application (like a GPS system in your car), you do not have to recalculate the route if you took a wrong turn. For this approach being efficient, you would have to pre-calculate a sub-graph to run your Dijkstra on. For real map data you also want to take into account one-way roads and interpret them in reversed orientation. During my studies we actually did exactly that on a map of one of Germany's states. It was amazing. However, we did not do the sub-graph-part which would have allowed us a bigger map (all of Germany or even Europe).
Very nice (other than the termination goof up). One thing I wish you had stated more explicitly is exactly why Dijkstra continues to go down the closest/cheapest paths to the finished set: because there can be no shorter path to those nodes from the source.
I love you Dr Mike Pound!
It's been over a year now. I'd like to see the foreshadowed sequel to this video.
Great demonstration, thanks a lot!
the last part was just amazing dude!
no way i could have found out the that problem/situation on my own
damn this guy is a legend for explaining it in such a simple manner.
This was on my final a few weeks ago.
Same. Algorithms class was super fun.
Mine was Networking, before that I had the algorithm on a CS based Mathematics final the year before.
There must be something off with me watching this on my free time on a holiday and enjoying this more than movies or shows
Excellent explanation!
Well explained, loved the video
Pathfinding algorithms always get referenced in the context of spaces and distances but its just as effective when dealing with abstract spaces, ones with dimensions that are defined manually. I imagine there are many problems that could be posed in the context of an abstract space that could be solved with these sorts of algorithms.
Dynamic programming problems comes to mind
I enjoy seeing my discrete math class coming into use!
Thanks! That was a really great explaination
Where do they the printer paper from? I remember that stuff from when I was a kid.I didn't know it was still made anymore.
Amazing explanation!
Thank you for the great explanation!
Mike rocks. Please do lot more videos
Computerphile and sleaford mods, Nottingham gets half of my TH-cam visits
The final step is wrong. You can't be sure that the first node to reach the destination is the shortest. What if instead of 2, the path from g to e was 100? It would still be the first to reach it, but would be far from the most efficient. You have to put e in the correct position in the priorities, and only when all shorter paths have been exhausted can you be sure it's the shortest path.
There's a related algorithm called Floyd's algorithm that calculates the shortest path between all nodes in a network, not just two points, that is used in practice for network design, routing etc.
LOVE THIS CHANNEL!!!
Very well explained!
Great Explanation Ever Sir 👍👍👍
What if the last weight was 10,000? Wouldn't it pick that as the fastest route then, despite it being much, much slower than by going through L?
Jeroen Bollen Yeah, actually the algorithm only terminates, when the destination node is finally processed, because that means that it is the unprocessed node with the shortest path to it and there cannot be a shorter path.
They kind of messed up in the video.
Another thing this missed was the fact that when Dijkstra's algorithm terminates, it will find the shortest path to all vertices in the graph from that starting point.
+TheSlimyDog
That depends whether you terminate when you process E (as they should have) or continue until you have processed all nodes. If you're looking for routes from London to Dover, you probably don't care about the best route to Edinburgh.
What Dijkstra's algorithm does give you is the best route to any processed node - your destination and anywhere cheaper to reach.
I'm sorry, that's correct. You can stop once E is at the top of your priority queue.
I should have mentioned earlier that, when deploying it "for real", Djikstra's algorithm is usually run until every available node has been processed, rather than terminating once you reach a designated destination simply because it is so easy to upgrade to A* and it offers such an improvement in performance if you do have a destination to aim for.
looking forward to another one ;)
Please, do some 3d graphics-related videos with Dr Mike Pound. I know there are already, but mr. Pound explains things so much better for me. Upvote if you agree
Dr. Pound should have his own channel. My new favorite youtube video series after PBS SPACE TIME and EEVBlog.
Please tell me you have a video addressing the "traffic jam" scenario you mentioned at the end!
Well with the A* you don't have the problem with going in the wrong direction for too long (still possible for a while) because you will keep the realworld distance in your heuristic function.
And one more thing, correct me if I'm wrong with this, but to be sure about that the found rout from S to E is indeed the shortest you would have to continue Dijakstra until every node is finished. So you can't stop when you found one route from S to E like in the example. In A* you can stop then.
Amazing video!
I like the pace of this video. They are usually much lower paced.
Thanks, this is useful.
I was thinking of solving the routing of a metro plan (finding the shortest path for a non existing "this should be the Brussels metro" plan) (website with Google Maps), using Dijkstra.
I liked this video, I have to tutor this algorithm and this gives me a nice cheeky way to explain it. Thank you.
doing Dijkstra’s Algorithm right now for an assignment... now to tern this into code
Education systems are using these public videos what a great time to be alive.
What?
@@gradientO ?
i just love computers some videos i don't understand a single thing but i love this channel
I am using this for my games, it is quite complicated then it seems. Its stats basically. I like this algorithm, its so much faster saving CPU power.
I'm really liking your tutorials; but would love to see some code as well!
THIS IS AWESOME I SERIOUSLY FINALLY UNDERSTAND THIS PART 2 PLEASE
\
just looking at some concepts ill face as a cs student (still in high school), I'm starting to reconsider my options
Great explanation. One thing though that would have been nice would have been if you guys showed the weight of all the edges instead of just the edges that a particular node is connected to.
I think you missed a crucial part near the end. You don't stop the algorithm as soon as you hit E. You only stop once E bubbles to the top of the sorted list, otherwise you might miss out on a faster pathway. For example if the connection from G to E had been a very large number, say 100, then the path going to the right would have been faster even though you got to E through G first.
More like this please.
Wow, you are sooooo cool. Thanks for your video!!!
the path to e is only guaranteed to be the shortest one if you put it in it's rightful place in the queue and go on until you reach it.
Super interesting example of how Dijkstra might be inefficient at the end!
Do a video about Levenstein distance next! (or other string comparing algorithms)
Is it possible to have an unordered list or a list that isn't a priority queue but instead whenever assigning which node we are going to evaluate now (or the current node), could I just use a for loop and iterate until I find the node in the list with the lowest cost and evaluate that node?
thanks man, it was amazing
Hey! I remember Dijkstra's algorithm from A level further maths! Back then I remember it being more complicated... seems really simple now...