Dijkstra's Algorithm - Computerphile

Key Takeaways

so what have we got here then Mike tell me tell me uh well we have a strange graph drawn out on my page a comment on a previous video asked about dkes the shortest path now I happen to have implemented D of shter path for one of piece of research I was doing a few years ago so I thought I'm at least somewhat place to have to give an opinion on it so let's talk about di shortage path um what it is where it's used and so on pathf finding algorithms are obviously quite important right we use them all the time on Google Maps or on our satnav system right there was a recent video on satellite navigation and how it works but of course that's only half the story 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 root planning also comes in on things like rooting so if you've got a network and lots of rooters what's the best way to root those packets through which ports to get to your destination the quickest so things like this now di the shortest path SE a lot of use in all of these things and extensions of it so for example a star 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 D shortage path 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 satav does when you say how do I get there right now each of these um nodes represents a junction so the vertices on the graph so a could be a roundabout B is a t Junction doesn't really matter uh actually B is more of a roundabout cuz it has four output 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 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 D implementation that I am familiar with and most D implantations um 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 faf you know four some maybe midle a roads right and this seven here that's you're falling in a Ford 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 country's massive Road Network we can't afford to do that right we have to be a bit smarter about how we look through um 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 missed one what Dyer 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 most sense based on how fast these roads are so check the quickest roads first so to do D we need a few things first of all we obviously need our graph right and when we need some some idea of how long the path is to let's say B once we've calculated it or something like that so at the very beginning of our search we have S we are at s s for start right 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 cost me nothing to get to S cuz I'm already there everything else I'll just put a couple out just to show you A 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 right and finally e is just the same distance 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 que each of these will have a distance but they're ordered also by that distance so the shortest ones at the top that's important and we we'll do it as we go through so let's start our search we start to S and we look through the neighbors of s and we say right well a it cost me seven to get to a right it's a bit of a pain so we were at zero distance cost was seven so now we're at seven right so a i scrap my Infinity and I write seven right so a is seven okay a is still the second shortest path currently because all the others are Infinity yeah B is 0+ two so that's two so let's just put a two in there this is all even though we haven't actually got to the end yet you just looking at numbers 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 CU 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 waiting of three so let's just find C in my list of of of course shuffled thingies there we go and hopefully how di Works will start to become clear once you see what I do next so see is three the only other thing that of course I forgot is while we're doing our search we have to keep a track of where we've been so B for example we know has a distance of two through the path s okay so s was the previous version right that's also true of a and also true of C now we swap C in a so now we have them in order all the others are still Infinity now s is done right so we can take s away and put it in our finished pile over here right s we don't about anymore the next St step is to see where is the current shortest path well it's B right B's 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 root through D which is shortest is is currently going through b and we'll put that in now six goes in just above a okay 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 q and currently the distance to a is seven right but actually the distance to B was two and the distance to a from B is three which is five so actually taking this detour here which looks longer is actually shorter because of this trie 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 we take our a and we say well now the root is five not seven it's decreased and it's no longer the shortest path from s to a it's from B so we scribble out s right my I'm getting too much text on these but we won't worry about it so a now overtakes D in our priority Q right uh so that's looking good okay h b had a length of two H has a length of one so H has a distance of three B is done right we've done B we we can count that as 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 l so L goes to C and it's 3 + 2 is 5 so L comes in just underneath a like this so C is 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 three so that's six via H and then G is H which is 3 + 2 so that's five a next we've already been to S we've already been to B so we start to get a little bit faster now with we've seen some stuff already what we're basically saying is we know what the shortest path to be is cuz we've already seen it so we can only look at new things so we look at d d is currently six via B A is currently five 5 + 4 is 9 which is bigger than D already is so we make no change the shortest path to D does not go through a so we don't worry about that okay a is done next up l l can't go to C we've already been there I and J both have a length of four so let's just find those to I and J need done all of them um right so these both go through L and they both have a path length of nine nine 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 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's got a distance of five 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 six 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 that 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 as found by D the idea is that if this graph were much much bigger you would prioritize looking down motorways first because they have less weight and you would um 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 they're going to be the shortest ones what you do is you get yourself to the M1 and start traveling down towards London as quickly as possible but that leades us to one last problem with dyra 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 an S and this is sort of M1 Junction right which to be about Junction 26 but we'll call this a right 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 dier doesn't build any idea of the direction you're traveling any kind of heris 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 satnav is be a little bit smarter don't start sort of look 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 and then red why not red right I think I've got them all E I think he's got to have a little checkered flag on isn't it well e yeah well how do I draw check a flag smiley face oh that means we're done right okay