8
Sep

Dijkstra’s Algorithm – Computerphile


(Sean:) So what we got here, Mike, tell me, tell me! (Mike:) Well, we have a strange graph drawn out on my page. A comment on a previous video asked about Dijkstra’s shortest path, now I happen to have implemented Dijkstra’s shorter path for one of the pieces of research I was doing a few years ago, so I thought: “I’m at least somewhat placed to have to give an opinion on it!” So let’s talk about Dijkstra’s shortest path, what it is, where it’s used, and so on. Path finding algorithms are obviously quite important — we use them all the time on Google maps or on our sat-nav system, all right, there was a recent video on satellite navigation and how it works, but of course that’s only half the story. (Mike:) Finding out where you are exactly is the first part of the problem, the second part is “I want to go over here, what’s the best route to do this?” Okay, route planning also comes in on things like routing, so if you’ve got a network and lots of routers what’s the best way to route those packets through which ports to get to your destination the quickest, so things like this — now Dijkstra’s shortest paths sees a lot of use in all of these things and extensions of it, so for example A* search — so I’ve drawn out an approximation of a road system on this piece of paper, so we’re going to use the analogy of roads for this one, because I think it’s a good — good example of types of shortest paths and we’re trying to start here, at S, and get down to E, right, this is broadly speaking, a small version of what a sat-nav does when you say: “How do I get there”, right? Now, each of these nodes represents a junction, so, the vertices on the graph, so, A could be a roundabout, B the T-junction — doesn’t really matter — actually B is more of a roundabout because it has four outputs — anyway, each of these numbers represents how hard it is to get along that road, so that in real life would be whether it was a motorway or a highway, whether it was a country road with a load of potholes, maybe there’s a tree down it and so you can’t get through that road, right, so in the Dijkstra implementation that I am familiar with, and most Dijkstra implementations, smaller is better okay, so broadly speaking this route here is kind of like our motorway right, twos, ones, that’s good, this one is a bit of a faff, you know, for some maybe mildly A-roads, right, and this seven here that you’re falling in a fort, and, you know, you’ve got water in the engine, and it’s bad. The question is “how do we find a route from here to here”, now, of course, this is a small graph so actually what we could just do is just search all the way through it by hand or using a very simple sort of brute-force search approach, and kind of get the best go, right, but if you think of the UK or the US or some other countries’ massive road network, we can’t afford to do that, right, we have to be a bit smarter about how we look through. And we also want to know absolutely that once we found a route, it is in fact the shortest route, and we didn’t just miss one. What Dijkstra does is basically similar to a sort of brute-force flood-fill search through this space, but does it in a kind of — in the order that makes the most sense, based on how fast these roads are, so it will check the quickest roads first. So to do Dijkstra, we need a few things, first of all we obviously need a graph right and then we need some — some idea of how long the path is, to let’s say B, once we’ve calculated it or something like it so at the very beginning of our search we have S, we are at S, (Sean:) As for start, right? (Mike:) It’s for start, yes, which confused me because some of the other letters are just in order and then these two aren’t, but anyway, S has a distance of zero, right, it costs me nothing to get to S because I’m already there, everything else — I’ll just put a couple out, just to show you, A, B and K have a distance of infinity because that basically says we haven’t looked yet, we don’t know how far, so for all we know it might not be possible to get there, no, and finally, E it’s just the same, it’s infinity, but with a smiley face to say that we’ve made it, right, now this structure here that I’m going to create is called a “priority queue”. Each of these will have a distance, but they’re ordered also by that distance, so the shortest one is at the top, that’s important, and we’ll do it as we go through. So let’s start our search, we start at S, and we look through the neighbors of S and we say “right, well, A, it costs me 7 to get to A”, right, it’s a bit of a pain. So, we were at 0 distance, it costs me 7, so now we’re at 7, right? So, A, I scratch my infinity, and I write 7, all right, so A is 7, okay, A is still the second shortest path currently because all the others are infinity. Yeah, B is 0+2 so that’s 2, so let’s just put a 2 in there. (Sean:) This is all even though we haven’t actually got to the end yet, you’re just looking at the numbers. (Mike:) we can’t get to E without having a look through all of these junctions, so this is what we’re doing, and we’re working our way in a smart way, now B is in this priority queue, but it has a lower number than A, so it takes its place at the top of a line, okay, so that’s good so far. Finally, the only other thing connected to S is C, which has got a weighting of three, so let’s just find C in my list, of course, shuffled thingies and there we go, and hopefully how Dijkstra works will start to become clear once you see what I do next, so C is three, the only other thing that of course I forgot, is while we’re doing our search, we have to keep track of where we’ve been, so B, for example, we know has a distance of two through the path S, ok, so S was the previous version, right, that’s also true of A, and also true of C. Now after we swap C and A so now we have them in order, all we have not seen is still infinity. Now, S is done, right, so we can take it away and put it in our finished pile over here, right, S we don’t need to worry about anymore. The next step, is to see where is the current shortest path, well it’s B, right, B has got the lowest number, so let’s start looking at B. So, if we look at B, we’ve already been to S, so we ignore it. We can go to D, so let’s put in a D, and D is the distance to B plus whatever this road is which is 6, 2 plus 4 is 6, and the route through D, which is shortest is currently going through B, and we’ll put that in, now 6 goes in just above A, ok, there we go. Now we can also go to B from A — we haven’t finished with A yet, it’s just sitting in this queue — and currently the distance to A is 7, right, but, actually, the distance to B was 2, and the distance to A from B is 3, which is 5, so actually, taking this detour here which looks longer is actually shorter, because of this tree on the line or something like that right, so remember, you know this isn’t representative of the actual physical distance from S to C. So we’ve updated D, and A is now shorter, right? So, we kept — we take our A, and we say “well now the route is 5, not 7”, it’s decreased and it’s no longer the shortest path from S to A, it’s from B, so look scribble out S, right, like, I’m getting too much technical needs but don’t worry about it. So, A now overtakes D in our priority queue, all right? So that’s looking good, okay, H, B had a length of 2, H has a length of 1, so H has a distance of 3, B is done, right? We’ve done B, we can count that as done, so C next, right, so we’re here. We can’t go to S, we can only go to L, that’s a nice, easy one. So I need to find out — so L goes to C and it’s 3 plus 2, it’s 5, so L comes in just underneath value like this, so C’s done So we look at H, and we say “what’s next from H”. We can look at F, so F will get 3 plus another 3, so about 6, via H, and then G is H, which is 3, plus 2 so that’s 5. A next, we’ve already been to S, we’ve already been to B. So we start to get a little bit faster now, we’ve seen some stuff, already. What we’re basically saying is, we know what the shortest path to B is, because we’ve already seen it so we can only look at new things, so we look at D, D is currently 6 via B, A is currently 5, 5 plus 4 is 9, which is bigger than the old D, so we make no change, the shortest path to D does not go through A, so we don’t worry about that, ok A’s done. Next up: L. L can’t go to C, we’ve already been there, I and J both have a length of 4, so that’s just fine, those two I and J — [I’m] needing all of them — right, so these both go through L, and they both have a path length of 9… 9 okay, so these go — and they’re both long, but they go in front of all the infinity ones. But — but down at the bottom here all right, the order isn’t important. So how [are] we doing, L is done, so then you can see what’s about to happen, right? We start with G, G has got a distance of 5, we’ve already been to H, let’s go to E, and so we say E goes back to G and has a length of 5, 6, 7, and we’re there, right? And then the final step is just to backtrack our route based on where we’ve been, so E goes to G — we can skip these, they aren’t used — G goes to H, H goes to B, and B Goes straight to S, and that is our shortest route through this graph, it’s found by Dijkstra, the idea is, that if this graph was much much bigger, you would prioritize looking down motorways first, because they have less weight, and you would prioritize physically short distances, anything that you can to try and make your search a bit quicker. When you’re searching to let’s say travel from Nottingham to London, you don’t look at the roads in Scotland, at least not first, Because it’s unlikely [that] they’re going to be the shortest ones. What you do is you get yourself to the M1 and start travelling down towards London as quickly as possible. That leads us to one last problem with Dijkstra, which is perhaps for another video? But I’ll just — I’ll just introduce it — if you imagine a situation where I’m at my house, and let’s say my house is here, at S, and this is sort of [the] M1 junction, right, which happens to be about junking 26? But we’ll call this A, alright, and then this is where I’m going in this direction, so lots of nodes along here, and there’s lots of nodes along here. And this is my destination down here on the end of this motorway. Because of a slight traffic jam, these all have slightly higher weights than these. Because Dijkstra doesn’t build any idea of the direction you’re traveling, any kind of heuristic about what you’re doing in a sort of smarter way, it’s going to look up here first, it’s going to travel all the way up this motorway as far as it can and only change direction when it becomes the shortest path to do so, so what you need to do if you’re going to actually implement a sat-nav, is be a little bit smarter — don’t start sort of looking to all the fast roads, look at the fast roads that are going roughly in the right direction because otherwise you might be wasting a lot of time.

Tags: , , , , , , , , , , , , ,

100 Comments

  • Joel Leung says:

    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?

  • Wandering Soul says:

    damn this guy is a legend for explaining it in such a simple manner.

  • Mark Freeman says:

    LOVE THIS CHANNEL!!!

  • ROBLOXowns Productions says:

    What you should check if you understood after watching this, is why you don't have to visit all the nodes and yet you've found the shortest path.

  • Peter Edwards says:

    I thought Dijkstra's Algorithm and others were more researched in path finding for games.

  • triton62674 says:

    10 too little frames to watch this video.
    For shame.

  • Aleksandr Hovhannisyan says:

    Why is Dijkstra's algorithm smart, though? Aren't we visiting all possible vertices either way, regardless of whether we examine freeways or residential streets first, for example?

  • Michał Gołuński says:

    I think there is a slight mistake in this explaination. When we get to E we actually don't know that it's the shortest path UNTIL we check all other that are shorter. In example from this video, IF there was a path from D to E with weigth 0, it would actually make S-E route faster.

  • Loosa Bway says:

    Enthusiastic, Knows his stuff I’m sure. But no teacher. Sorry.

  • Maaruks says:

    this is the best explanation

  • Mohamed Abdelaziz says:

    more than amazing

  • Billy Armfield says:

    why would you search all the adjacent vertices of B before checking C (last remaining adjacent vertex of S)?

  • RedMikePumpkin says:

    Bs = 2 =DChcSEwjUgeGRr5nRAhUetsAKHcBpALUYABAR&sig

  • First Last says:

    This guy really grew on me.

  • Mason Pickering says:

    You can find Dijkstra in the bath house in Novigrad

  • Source Intelligentsia says:

    please Dr. Pound my brain!

  • Siva Prakash says:

    Mike rocks. Please do lot more videos

  • José Almeida says:

    How can i predict the direction of the path to avoid the last problem?

  • Wen Chu says:

    chaotic explanation !

  • bigcheesetaste says:

    Could it be, maybe, Dijkstra's final aeon?

  • Tunturisorsa says:

    well doesn't this video come at a handy time

  • benny b says:

    Please stop shaking the camera

  • Maximilian Faust says:

    some quick maths

  • DepressedNOF says:

    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.

  • HitmanBobina47 says:

    Did mike's face get borked?

  • Q Squared says:

    TIL OSPF is a dijkstra algorithm

  • Ahanaf Rakin says:

    ece297 squad

  • - _ LIR _ - says:

    How to implement infinity in c++ ?

  • Akshay Sapra says:

    at 5:01, shouldnt C be brought to the 2nd top because its a priority queue?

  • Yashsvi Dixit says:

    I was like Mike Pound but then I joined college and every brain activity just died

  • Udi Matalon says:

    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.

  • Pankaj Kumar says:

    the guy is smart.

  • Ben Trono says:

    This is a great video, but technically this algorithm would continue to run until E is removed from the queue, rather than stopping once E is assigned its first distance. The Algorithm would remove/visit nodes D and F, and then finally E.

    (to anyone just learning) There are cases where the first distance assigned to E is not the shortest, like if this same graph was manipulated to have an edge from G to E worth 3 instead of 2, and an edge from F to E worth 1. But once E has the shortest distance in the queue, it is guaranteed that the shortest path to E has been found.

  • Marc Grec says:

    What is the difference between Lee's Algorithm and this one?

  • Ege Ersü says:

    Why didn't you just associate the numbers with distances? Would have been much easier.

  • Ege Ersü says:

    When he is refering to things on the graph, it doesn't make any sense to cut to his face. We need to see the nodes and edges he is talking about.

  • Saurabh Moharir says:

    Smart Man!!

  • __ says:

    lol hokkams razor in algorithm form xD

  • ItTakesOne ToCatchOne says:

    I think that some clarifications (annotations or something like that) should be made with regards to the erroneous implementation.

  • Atul Koshta says:

    What a lovely explanation Dr. Mike!

  • Akasuki says:

    1080p50 is butter.

  • a8lg6p says:

    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.

  • Pr1celess Path says:

    First time I saw your videos lol you are like Dan Brown the NLP (Neuro Linguistic Programming) expert who could ask you for directions (likely to a place nearby that he knows damn well already how to get there) simultaneously using body movements of need vs charity insinuates using non-verbal means of convincing you that you should give him your wallet because he was in need that you held his water as a favor. How the water, the wallet and asking for directions to the library are related, is even more baffling that he was able to succeddfully pull it off without fail 3 times in a row the 3rd attempt the more amazing. His explaination of why you hand the wallet over to him is mixing math, science, misdirection, sleights, slight of hand (gypsy theif), combined with psychology, sociology, and communication devices (metaphors, alliteration, and creative entertaining sentence patterning) to be dazzle you into appreciating him rather than the reason he has approached you: TO TRICK YOU. Look that guy up he is the splitting image of you.

  • Tamir Cohen says:

    Wouldn't you multiply the actual distance in KM to a junction by the difficulty to travel there to get an accurate number telling you the "cost" to travel to that junction?

  • byron perez says:

    allways amazed when someone explains computer science without a computer

  • raghu chakkamadam says:

    Has the traveling salesman problem been solved yet?

  • Grant Bowen says:

    Dijkstra… Witchering intensifies

  • code_dredd says:

    It's been over a year now. I'd like to see the foreshadowed sequel to this video.

  • TransparentLabyrinth says:

    I feel like pathfinding algorithms make less sense the more explanations I watch of them. T_T

  • kon kos says:

    you should really do more pathfinding algorothms like bfs dfs primm etc

  • LBGST zockt says:

    I understood some of thoose words…

  • Mike West says:

    I can't follow the diagram because whomever edited this video felt they need to keep cutting back and forth to his face. The result is very confusing and hard to follow

  • Theodore Tang says:

    Wow, you are sooooo cool. Thanks for your video!!!

  • Keith Desouza says:

    Nicely explained. There is still something confusing. The overloaded use of the numbers between the nodes. Is that number, the weight (speed) of the road or is it the distance between nodes?

  • Bikal says:

    50 fps gang

  • Tashlif says:

    gettt intoo the pointtt maaannn you speakk soo muchh

  • sting281 says:

    One of the best algorithms ever. Respect, respect and only respect.

  • Philip Kertsman says:

    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.

  • Skyy 95 says:

    ♥♥♥

  • Flux Capacitor says:

    Dr. Pound should have his own channel. My new favorite youtube video series after PBS SPACE TIME and EEVBlog.

  • Dr. Harish Ravi says:

    Great demonstration, thanks a lot!

  • SandroRocchi says:

    Dr Mike eyeballed that neither I or J would get to E faster than G, and skipped to the end when an algorithm would not have been able to, without knowing the cost of getting to K. In this example we're talking about moving in the physical world, but most of the things we use shortest paths algorithms for can actually have a negative weight, so if we had a -100 cost between J and K, that path would be so fast we'd arrive there before we even left, and Dr. Mike refused to discover time travelling. Jokes aside: this algorithm isn't finished before you know the cost of arriving at every node in the graph.

  • LIKE YOU IAM says:

    finally an approach that takes into account the practical implementation. Thanks for mentioning the "priority queue"!
    One quesion is still left for me: WHERE is the algorithm running? Is it always running at 's' and the priority queue gets updates from the other nodes? Or is the priority queue copied to other nodes?
    I guess both would be possible, the former probably being easier to implement

  • Tijs Perdaems says:

    As a Dutchie, I like your pronounciation of Dijkstra xD

  • Joseph Peters says:

    He messes with alot of stuff

  • Mum Blic says:

    Nice to see that my own created algorithm is similar, … well exactly the same and it has even a name ;-))

  • Jean-Nay Mar says:

    Right ?

  • Gladiator Mediator says:

    Frodo is trying to find shortest path to Mordor, sneaky hobbitses!

  • Ahmed Yassien says:

    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 <3

  • Samah Samiee says:

    How are those numbers even decided?.?

  • Mihaela Costea says:

    how come you jumped from C to H?

  • Dave J says:

    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.

  • Rasyid Al Faruqi says:

    his voice really fits to teach

  • Nathan Patera says:

    -1, disliked for too much camera jumping. Hard to focus when I keep seeing different camera angles. Good content though, but not worth the pain of watching…

  • Jim Giant says:

    6:58 The virgin A* vs Chad Dijkstra's Algorithm

  • Zaid Khan says:

    The last part is worth the mistake he made about the recursion ending abruptly.

  • The Wiedźmin says:

    Now how the hell am I supposed to code this algorithm ?!

  • The Wiedźmin says:

    I taught Dijkstra was in the Witcher universe and not a real man solving math problems…

  • Joe Stevenson says:

    so the prioty queue would be a heap, right?

  • Razman Sarit says:

    You know what dude, you're like Jamie Oliver, but with complex algorithms

  • Raymond says:

    more videos please 😀

  • Stanley Backlund says:

    I love how a guest has never looked into the camera on this channel

  • the one who never gave up says:

    he is in my age and he has a PhD while this is my first year sc engineering and barely gonna make it ,jez i wish i never was born.

  • Apro Dan says:

    Does anyone know a method to get to the endpoint even if almost all nodes are intertwined? I feel like using cards would take forever. So what else could we use?

  • Sinan Akkoyun says:

    We're all here for Pathfinder

  • Marco Aurélio Lima do Nascimento Junior says:

    wow, really interesting

  • Endrit Shabani says:

    I always thought Dijkstra was an Indian xD

  • Recycle Bin says:

    how to win at flow free

  • Shadab Sarvar says:

    TIL how to Djikstra is pronounced, my Indian professors sounds completely different. Still having trouble speaking that word.

  • Арсений Буров says:

    This is my favorite guy of them all! Thanks for the content!

  • Keshav Sharma says:

    Dijkstra's Algorithm finds the shortest path between two points X
    well the above statement is not really correct,
    its a single-source shortest path algorithm and so given some vertex/node V, it finds shortest distance from V to all other nodes in the graph.

  • Nate Higgers says:

    Pathfinding in minecraft is very important

  • Ben Jordan says:

    How do you calculate the numbers between the paths in real world navigation like an OpenStreetMap service? You explained that it is not exactly the distance between two points, but more the "difficulty" of a road. But do you take the distance then and multiply it by a difficulty factor (eg. 1 for highway and 2 for small road with a speed limit of 65 km/h 2 times lower than the estimated speed of the car driving on the highway without speed limit = 130km/h)?

  • M Neztsosie says:

    I suppose this is used for cell towers taking into account var

  • LivingBlast, LLC says:

    I'm seriously convince that dry-erase boards have not been discovered in the UK

  • JDines says:

    While a router can use OSPF to determine which next hop to send the packet there is no guarantee the path calculated by source router will be the actual path the packet takes.

  • Chandra Chud says:

    Great way to explain it.

  • dubstep1994 says:

    Maybe he should re record it in a much simpler way. And with correct line distances according to time it takes to travel the distance. Too much noise.

  • Snoopy1alpha says:

    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).

Leave a Reply

Your email address will not be published. Required fields are marked *