# Dijkstra's Algorithm - Computerphile

580K+ views   |   12K+ likes   |   205 dislikes   |
10:42   |   Jan 04, 2017

### Transcription

• (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.

### Description

Dijkstra's Algorithm finds the shortest path between two points. Dr Mike Pound explains how it works.

How Sat Nav Works: /watch?v=EUrU1y5is3Y
Slow Loris Attack: /watch?v=XiFkyR35v2Y

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham: http://bit.ly/nottscomputer

Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com

### Related videos

05:50
7M+ views | May 20, 2013
00:00
386K+ views | Jul 06, 2018
00:00
612K+ views | Feb 24, 2017
14:18
592K+ views | May 31, 2017
00:00
958K+ views | Feb 11, 2019

### Suggested videos

10:52
316K+ views | May 07, 2016
13:13
697K+ views | Aug 04, 2015
00:00
247K+ views | Sep 02, 2016
00:00
2M+ views | Apr 02, 2015
00:00
508K+ views | Jan 27, 2017
20:00
793K+ views | Mar 03, 2017
24:01
4M+ views | Nov 07, 2016
15:14
450K+ views | Feb 07, 2018

### Trending videos

00:00
Jan 18, 2020 at 01:08
00:00
Jan 23, 2020 at 11:57
00:00
Jan 23, 2020 at 01:00
07:08
456K+ views | yesterday at 05:01

03:42
9M+ views | Feb 07, 2019
00:00
yesterday at 09:24