1:27

So if you had a path like this with three edges and length one, two and

Â three, then the length of the path would just be six.

Â And then we define the shortest SV path in the natural way, so amongst all of

Â the paths directed from S to V, each one has its own respective path length and

Â then the minimum overall SV paths is the shortest path distance in the graph G.

Â So I'm going to make two assumptions for these lectures.

Â One is just really for convenience, the other is really important.

Â The other assumption, without which,

Â Dijkstra's algorithm is not correct, as we'll see.

Â 2:01

So for convenience we'll assume that there is a directed path from

Â S to every other vertex V in the graph,

Â otherwise the shortest path distance is something we define to be plus infinity.

Â And the reason this is not a big assumption is,

Â if you think about it, you could detect which vertices are not reachable from

Â S just in a preprocessing step using, say, breadth-first or depth-first search.

Â And then you could delete the irrelevant part of the graph, and

Â run Dijkstra's algorithm as we'll describe it on what remains.

Â Alternatively, Dijkstra's algorithm will quite naturally figure out

Â what vertices there are paths to from S and which ones there are not, so

Â this won't really come up.

Â So to keep it simple, just think about we have an input graph

Â where you can get from S to V, for every different vertex V.

Â And the challenge then is amongst all the ways to get from S to V,

Â what is the shortest way to do it?

Â 3:05

Now in the context of a driving directions application

Â it's natural to ask the question why would you ever care about negative edge lengths.

Â Until we invent a time machine that doesn't seem like

Â negative edge lengths are going to be relevant when you are computing literal

Â paths through literal networks.

Â But again remember that paths can be thought of as more abstractly as a just

Â sequence of decisions.

Â And some of the most powerful applications of shortest paths

Â are coming up with optimal weight such sequences.

Â So, for example, maybe you're engaging in financial transactions and

Â you have the option of both buying and selling assets at different times.

Â If you sell then you get some kind of profit and

Â that would correspond to a negative edge length.

Â So there are quite interesting applications in which negative edge

Â lengths are relevant.

Â If you are dealing with such an application,

Â Dijkstra's algorithm is not the algorithm to use.

Â There's a different shortest path algorithm, a couple other ones.

Â But the most well-known one is called Bellman-Ford.

Â That's something based on dynamic programming,

Â which we may well cover in a SQL course.

Â Okay, so for Dijkstra's algorithm, we always focus on graphs.

Â That'll have only non-negative edge lengths.

Â So, with the next quiz, I just want to make sure that you understand the single

Â source shortest path problem.

Â Let me draw for you here a simple four node network, and ask you for,

Â what are the four shortest path lengths.

Â So from the source vertex s, to each of the four vertices in the network.

Â All right, so the answer to this quiz is the final option, 0,1,3,6.

Â To see why that's true, well,

Â all of the options had 0 as the shortest-path distance from s to itself.

Â So that just seemed kind of obvious.

Â So the empty path will get you from s to itself and have 0 length.

Â No suppose you wanted to get from S to V, well there's actually only one way to do

Â that, you have to go along this one hop path.

Â So the only path has length of one, so the shortest path distance from S to V is one.

Â Now W's more interesting, there's a direct one hop path, SW,

Â that has a length of four, but that is not the shortest path from S to

Â W Inf act to two-hop path that goes through v as an intermediary has

Â total path length three which is less than the length of the direct arc from s to w.

Â So therefore the shortest distance from s to w is going to be 3.

Â And finally for the vertex t there's three different paths going from s to t.

Â There's the two-hop path that goes through v.

Â There's the two hop path which goes through w, both of those have path length

Â 7, and then there's the three hop path which goes through both v and w.

Â And that actually has a path length of one plus two plus three equals six.

Â So despite having a largest number of edges, the zigzag path is, in fact,

Â the shortest path from s to t and it has length 6.

Â All right, so before I tell you how Dijstrka's algorthin works,

Â I feel like I should justify the existence of this video a little bit.

Â All right?

Â Because this is not the first time we've seen shortest paths.

Â You might be thinking rightfully so.

Â We already know how to compute shortest paths.

Â That was one of the applications of breadth first search.

Â 6:30

So for example, in the graph that we've explored in the previous quiz,

Â if we ran breadth first search, starting from the vertex s,

Â it would say that the shortest path distance from s to t is 2 and

Â that's because there's a path with two hops going from s to t.

Â Put differently, t is in the second layer emanating from s.

Â But as we saw in the quiz, there's not in fact

Â a shortest two hop path from s to t if you care about the edge lengths.

Â Rather the minimum length path, the shortest path, with respect to the edge

Â weights, is this three hop path which gives us a total length of 6.

Â So breadth first search is not going to give us what we want

Â when the edge lengths are not all the same.

Â And if you think about an application like driving directions, then needless to say,

Â it's not the case that every edge in the network is the same.

Â Some roads are much longer than others,

Â some roads will have much larger travel times than others, so

Â we really do need to solve this more general shortest path problem.

Â Similarly, if you're thinking more abstractly about a sequence of decisions

Â like financial transactions,

Â in general different transactions will have different values.

Â So you really want to solve general shortest paths,

Â you're not in the special case that breadth-first search solves.

Â 7:48

General edge weights, unit edge weights, it's basically the same.

Â Say you have an edge that has length three.

Â How is that fundamentally different than having a path with three edges,

Â each of which has length one?

Â So why not just replace all the edges with a path of edges of the appropriate length?

Â Now we have a network in which every edge has unit length and

Â now we can just run breadth-first search.

Â So put succinctly, isn't it the case that computing shortest paths with general

Â edge weights reduces to computing shortest paths with unit edge weights?

Â Well, the first comment I want to make is I think this would be an excellent

Â objection to raise.

Â And indeed, as programmers, as computer scientists,

Â this is the way you should be thinking.

Â If you see a problem that seems superficially harder than another one,

Â you always want to ask, well, maybe just with a clever trick I can reduce it

Â to a problem I already know how to solve.

Â That's a great attitude in general for problem solving.

Â And indeed, if all of the edge lengths were just small numbers, like 1, 2, and

Â 3 and so on, this trick would work fine.

Â 8:49

The issue is when you have a network where the different edges can have very

Â different lengths.

Â And that's certainly the case in many applications.

Â Definitely road networks would be one where you have both sort of long

Â highways and you have neighborhood streets.

Â And potentially in financial transaction based networks you would also have a wide

Â variance between the value of different transactions.

Â And the problem then is some of these edge lengths might be really big.

Â They might be 100, they might be 1,000.

Â It's very hard to put operating bounds on how large these edge weights could be.

Â So if you start wantonly replacing single edges with these really long paths

Â of like 1,000, you've blown up the size of your graph way too much.

Â So you do have a faithful representation of your old network, but

Â it's too wasteful.

Â So even though breadth-first search runs in linear time,

Â it's now on this much larger graph.

Â And we'd much prefer something which is linear time or

Â almost linear time that works directly on the original graph.

Â And that is exactly what Dijkstra's shortest-path algorithm

Â is going to accomplish.

Â 9:49

So this is another one of those algorithms where no matter how many times I explain

Â it, it's always just super fun to teach.

Â And the main reason is because it exposes the beauty that pops up in good algorithm

Â design.

Â So the pseudocode, as you'll see in a second, is itself very elegant.

Â We're just going to have one loop, and in each iteration of the loop we will compute

Â the shortest path distance to one additional vertex.

Â And by the end of the loop we'll compute shortest path distances to everybody.

Â The proof of correctness, which we'll do in the next video, is a little bit subtle,

Â but also quite natural, quite pretty.

Â And then finally, Dijkstra's algorithm will give us our first opportunity to see

Â the interplay between good algorithm design and good data structure design.

Â So with a suitable application of the heap data structure,

Â we'll be able to implement Dijkstra's algorithm so it runs blazingly fast,

Â almost linear time, namely m times log n.

Â But I'm getting little ahead of myself.

Â Let me actually show you this pseudocode.

Â 10:43

At a high level, you really should think of Dijkstra's algorithm as being a close

Â cousin of breadth-first search.

Â And indeed, if all of the edge lengths are equal to one,

Â Dijkstra's algorithm becomes breadth-first search.

Â So this is sort of a slick generalization of breadth-first search

Â when edges can have different lengths.

Â So like our generic graph search procedures, we're going to start at

Â the source vertex s, and in each iteration we're going to conquer one new vertex.

Â And we'll do that once each iteration after m minus1 iteration, we'll be done.

Â And in each iteration will correctly compute the shortest path distance

Â to one new possible destination vertex v.

Â 11:58

Now to help you understand Dijkstra's algorithm,

Â I'm going to do some additional bookkeeping which you would not do

Â in a real implementation of Dijkstra's algorithm.

Â Specifically, in addition to this array capital A in which we

Â compute shortest path distances from the source vertex to every other destination,

Â there's going to be an array capital B in which we'll keep track

Â of the actual shortest path itself from the source vertex s to each destination v.

Â So the arrays A and B will be indexed in the same way.

Â There'll be one entry for each possible destination vertex v.

Â Capital A will store just a number for each destination, shortest path distance.

Â The array B in each position will store an actual path,

Â so the shortest path from s to V.

Â But again, you would not include this in an actual implementation.

Â I just find in my experience it's easier for students to understand this algorithm

Â if we think of the paths being carried along as well.

Â 12:49

So now that I've told you the semantics of these two arrays,

Â I hope it's no surprise how we initialize them for the source vertex itself, s.

Â The shortest path distance from s to itself is 0.

Â The empty path gets you from s to s with length 0.

Â There's no negative edges by assumption, so

Â there's no way you can get from s back to s with a non-positive length, so

Â this is definitely the shortest path distance for s.

Â By the same reasoning,

Â the shortest path from s to s is just the empty path, the path with no edges in it.

Â 14:09

So that motivates that a given iteration of the while loop

Â to look at the stuff we've already process, that's X, and

Â the stuff we haven't already processed, that's v minus X.

Â s, of course, starts in X and we never take anything out of X, so

Â s is still there.

Â In some generic iteration of the while loop,

Â we might have some other vertices that are in X.

Â And in a generic iteration of this while loop,

Â there might be multiple vertices which are not in X.

Â And now, as we've seen in our graph search procedures, there are general or

Â edges crossing this cut.

Â So there are edges which have one endpoint in each side, one endpoint in X and

Â one endpoint outside of X.

Â This is a directed graph so they can cross in two directions.

Â They can cross from left to right or they can cross from right to left.

Â 14:51

So you might have some edges internal to X.

Â Those are things we don't care about at this point.

Â You might have edges which are internal to v- X.

Â We also don't care about those, at least not quite yet.

Â And then you got edges which can cross from X to v-X,

Â as well as edges that can cross in the reverse direction, from v -X back to X.

Â And the ones we're going to be interested in, just like when we did graph search and

Â directed graphs, are the edges crossing from left to right,

Â the edges whose tail is amongst the vertices we've already seen and

Â whose head is some not yet explored vertex.

Â 15:28

So the first idea is that in each iteration of the while loop we scan, or

Â we examine, all of the edges with tail in X and head outside of X.

Â One of those is going to lead us to the vertex that we pick next.

Â So that's the first idea, but now we need a second idea,

Â because this is again quite underdetermined.

Â There could be multiple such vertices which meet this criterion.

Â So for example, in the cartoon in the bottom left part of this slide,

Â you'll notice that there's one vertex here.

Â Which is the head of an arc that crosses from left to right.

Â And there's yet another vertex down here in v minus x,

Â which again is the head of an arc which crosses from left to right.

Â There are two options of which of those two to suck into our set x and

Â we might want some guidance about which one to pick next.

Â The key idea in Dijkstra is to give each vertex a score

Â corresponding to how close that vertex seems to the source vertex s, and

Â then to pick among all candidate vertices, the one that has the minimum score.

Â Let me be more precise.

Â 17:15

For example, in the cartoon in the bottom left,

Â maybe of the two edges crossing from left to right, maybe the top one

Â is the one that has a smaller value of Dijkstra's greedy criterion.

Â In that case, this would be the vertex v star and

Â the other end of the edge would be the vertex w star.

Â This edge, v star, w star is going to do wonders for us.

Â It will both guide us to the vertex that we should add the x next,

Â that's going to be w star.

Â It's going to tell us how we should compute the shortest path distance to w

Â star, as well as what the actual shortest path from s to w star is.

Â Specifically, in this iteration of the wild loop, after we've chosen this edge v

Â star w star, we add w star to x.

Â 18:22

What we're going to do is we're going to set the r estimate

Â of w star's shortest path distance from s to be equal to

Â the value of this Dijkstra's greedy criterion for this edge.

Â That is, whatever our previously computed shortest path distance from s to v star

Â was plus the length of the direct edge from v star to w star.

Â Now a key point is to realize that this code does make sense.

Â By which I mean,

Â if you think about this quantity A(v), this is been previously computed.

Â And that's because environ of this algorithm is we've always computed

Â shortest path distances to everything that is in capital X.

Â And of course, the same thing holds when we need to assign w star shortest path

Â distance because v star was a member of capital X,

Â we had already computed its shortest path distance.

Â So we can just look up the v star entry position in the array a.

Â Over in our picture on our left, we would just say,

Â what did we compute the shortest path distance to v star previously?

Â Maybe it's something like 17.

Â And then we'd say, what is the length of this direct edge from v star to w star?

Â Maybe that's 6.

Â Then we would just add 17 and 6 and

Â we would put 23 as our estimate of the shortest path distance from s to w star.

Â 19:36

We do something analogous with the shortest path itself in the array b.

Â That is, again, we're responsible, since we just added w star to capital X,

Â we're responsible for suggesting a path from s to w star in the b array.

Â What we're going to do is we're just going to inherit the previously computed path

Â to v star and we're just going to tack on the end one extra hop,

Â namely the direct edge from v star to w star.

Â That will give us a path from s all the way to w star via v star

Â as an intermediate pit stop and that is the entirety of Dijkstra's Algorithm.

Â I've explained all of the ingredients about how it works at a conceptual level.

Â The two things I argue is, why is it correct?

Â Why does it actually compute shortest paths directly to all of the different

Â vertices, and then secondly, how fast can we implement it?

Â The next two videos are going to answer both of those questions but

Â before we do that, let's go through an example to get a better feel for

Â how this algorithm actually works.

Â I also want to go through a non example so

Â that you can appreciate how it breaks down when there are negative edges, and

Â that'll make it clear why do we need a proof of correctness because it's not

Â correct without any assumptions about the edge lengths.

Â