0:00

In this video, I'll prove to you that Dijkstra's algorithm does indeed

Â compute to correct shortest paths in any directed graph

Â where all edge links are non negative.

Â So let me remind you about what is Dijkstra's algorithm, it's very much in

Â the spirit of our graph search primitives, in particular breath first search.

Â So there's going to be a subset x of vertices,

Â which are the ones that have been processed so far.

Â Initially x contains only the source vertex.

Â Of course the distance from the source vertex to itself is 0,

Â and the shortest path from s to itself is the empty path.

Â So then we'll have a main while loop, that's going to be n-1 iteration, and

Â each iteration will bring one vertex which is not currently in x into capital X.

Â 0:39

And a variant that we are going to maintain,

Â is that all the vertices in x we will have computed estimates of the shortest path

Â distance from x to that vertex and

Â also we'll have computed the shortest path itself from x to that vertex.

Â Remember our standing assumption stated in the previous video,

Â we're always going to assume there's at least one path from the source vertex s to

Â every other destination v.

Â Our job is just to compute the shortest one.

Â And also, we have to assume that the edge links are non negative

Â as we've seen otherwise Dijkstra's algorithm might fail.

Â Now, the key idea in Dijkstra's algorithm is a very careful

Â choice of which vertex to bring from outside of x into capital X.

Â So what we do is we scan the edges crossing the frontier.

Â Meaning given the current edges vertices that we've already processed,

Â we look at all of the edges whose tail has been processed and

Â whose head has not been processed.

Â So the tails in capital X, the head is outside of x that is,

Â they cross the cut from left to right in the diagrams that we usually draw.

Â 1:40

Now, there may be many such edges.

Â How do we decide amongst them?

Â Well, we compute the Dijkstra's greedy score for each.

Â The Dijkstra greedy score is defined as the shortest path distance we computed for

Â the tail and that's been previously computed because the tail's in capital X.

Â And then we add to that the length contributed by this edge itself by

Â the edge vw which is crossing the cut from left to right.

Â So amongst all edges crossing the cut from left to right we compute all those

Â Dijkstra greedy scores we pick the edge with the smallest greedy score Calling

Â that edge just v* w*.

Â For the purposes of notation, w* is the one that gets added to x.

Â So it's the head of the arc for the smallest three score, and then we compute

Â the shortest path distance of that new vertex w* to be the shortest path distance

Â to v* plus the length contributed by this edge v* w* and then was the shortest path.

Â It's just the shortest path previously computed to v star

Â plus this extra edge v* w* tacked onto the end.

Â Here's the formal statement we're going to prove.

Â 2:56

So the claim is that for every directed graph, not just the four node,

Â five arc example we studied.

Â As long as there's no negative edge links, Dijkstra's algorithm works perfectly.

Â It computes all the correct shortest path distances.

Â So just to remind you about the notation,

Â what does it mean to correct all shortest path distances correctly?

Â It means that what the algorithm actually computes,

Â which is a(v), is exactly the correct shortest path distance,

Â which we were denoting by L(v) in the previous video.

Â 3:28

Both the algorithm and the proof of correctness where established by

Â Esther Dijkstra this was back in the late 1950s.

Â Dijkstra was a Dutch computer scientist, and certainly

Â one of the forefathers of the field as a science, as an intellectual discipline.

Â He was awarded the ACM Turing award, so

Â that is the Nobel Prize in computer science effectively.

Â I believe it was 1972, and he worked a long time in the Netherlands,

Â but then also spent a lot of his later career at UT Austin.

Â So the way this proof is going to go is going to be by induction.

Â 4:01

And basically, what we're going to do is we're going to say every iteration,

Â when we have to commit to shortest path distance to some new vertex,

Â we do it correctly.

Â And so then the form of the induction will be,

Â well given that we made all of our previous decisions correctly,

Â we computed all our earlier shortest paths in the correct way.

Â That remains true for the current iteration.

Â So formally, it's induction on the number of iterations of Dijkstra's algorithm.

Â And as is more often than not the case in proofs by inductions the base case

Â is trivial.

Â So that just says before we start the y loop, what do we do?

Â Well we commit to the shortest path distance from s to itself.

Â We set it to 0, we set the shortest path to be the empty path,

Â that is of course true.

Â Of course,

Â even here we're using the fact that there are no edges with negative edge length.

Â That makes it obvious that sort of having a non empty path can get you negative

Â edge length better than 0.

Â 4:49

So the first choice path computation we do s to s is trivially correct.

Â The hard part of course is the inductive step justifying all of the future

Â decisions done by the algorithm.

Â And of course, mindful of that example that not example we had at the end of

Â the previous video in the proof by induction,

Â we'd better make use of the hypothesis that every edge has non negative length.

Â Otherwise the theorem would be false.

Â So we better somewhere in the proof use the fact that edges cannot be negative.

Â 5:29

Let's be a little bit more formal about that.

Â So that is everything we computed in the past.

Â What did we compute in the past?

Â Well for each vertex which is in our set capital X for each vertex that

Â we've already processed, we want to claim that our computed shortest path distance

Â matches up exactly with the true correct shortest path distance.

Â So in our running notation, for every already processed vertex, so for

Â all vertices v, in our set capital X.

Â What we computed as our estimate of the shortest path distance for

Â v is in fact, the real shortest path distance.

Â 6:05

And also, the computed shortest path is in fact,

Â a true shortest path from s to v.

Â So again remember, this is a proof by induction.

Â We are assuming this is true,

Â and we're going to certainly make use of this assumption

Â when we establish the correctness of the new iteration, the current iteration.

Â What happens in an iteration?

Â Well, we pick an edge which we've been calling v* w*.

Â 6:44

So by the definition of the algorithm we assign as a shortest path from s to w*.

Â The previously computed purportedly shortest path from s to v*,

Â and then we tack on the end the direct arc, v* w*.

Â So pictorially, we already had some path

Â that started at s and ended up at v*, and

Â then we tack on the ends this arc going to w* in one hop.

Â And this whole shebang is what we're going to assign as B of w*.

Â So let's use the inductive hypothesis.

Â Inductive hypothesis says that all previous iterations are correct.

Â So that is any shortest path we've computed in a previous iteration

Â is in fact a bona fide shortest path from the source x to the vertex.

Â Now v*, remember is in x.

Â So that was previously computed.

Â 7:45

So by the inductive hypothesis, this path bv*,

Â from s to v*, is in fact a true shortest path from s to v* in the graph.

Â So therefore, it has length l of v*.

Â Remember, l of v* is just by definition the true shortest

Â path distance in the graph from s to v*.

Â Now, given that the path that we've exhibited s to w*,

Â is just the same one as we inherited the v* plus this extra edge tacked on.

Â It's pretty obvious what the length of the left hand side is.

Â It has length, just the length of the old path which we just argued is the shortest

Â path distance from sw* plus the length of this arc that we tacked on.

Â That's going to be lv* w*.

Â 8:30

So by the definition of the algorithm,

Â what we compute for w* is just the Dijkstra's greedy score which is just

Â the computer choice path distance to the tail.

Â The v* plus the length of the direct edge.

Â By the inductive hypothesis,

Â we've correctly computed all previous choice path distances.

Â V* is something we computed in the past by inductive hypothesis is correct.

Â So this is equal to l of v* by the inductive hypothesis.

Â So don't worry if you're feeling a little lost at this point.

Â We've actually really done no content in this proof yet.

Â We haven't done the interesting part of the argument.

Â All we've been doing is setting up our dominoes,

Â getting them ready to be knocked down.

Â So what have we done in the current iteration?

Â 9:10

Well first of all, our estimate of the shortest path distance from the source to

Â w*, to the new vertex that we're including in the set capital X,

Â is the true shortest path distance to v* plus the length of the edge from v* to w*,

Â that's the first thing.

Â Secondly, the path that we have in the v array

Â is a bona fide path from s to w* with exactly this distance.

Â 9:34

And the point is, now it's clear what has to be proven for

Â us to complete the inductive step and

Â therefore, the proof of correctness of Dijkstra's algorithm.

Â So what do we need to proof?

Â We need to proof that this isn't just any old path that we've exhibited from

Â s to this vertex w*, but that it's the shortest path of them all.

Â But differently we need to show that every other sw* pattern

Â in this graph has length at least this circled value.

Â 10:04

So let's proceed let's show that no matter how you get from the source for

Â test to this destination w*.

Â The total length of the path you travel is going to be at least this circled value,

Â at least L(v*) + lv*w*.

Â Now on the one hand, we don't have a lot going for us,

Â because this path P could be almost anything.

Â It could be a crazy looking path.

Â So how do we argue that it has to be long?

Â Well, here's the one thing we've got going for us for

Â any path P that starts in s and goes to w*.

Â Any such path must cross the frontier.

Â Remember, it starts on the left side of the frontier, it starts at the source

Â vertex, which is initially and forever in the set capital X.

Â And remember that we only choose edges that cross the frontier whose head

Â is outside of x.

Â And w* is exactly the head of the edge we chose in this iteration,

Â so this is not an x.

Â 11:07

So let's think about the graph and it's two pieces,

Â that it's the left of the front tier and not to the right.

Â The stuff is already processed and the stuff which is not been processed.

Â S of course, is on the left hand side, and

Â at the beginning of this iteration of the while loop, w* was on the right hand side.

Â 11:45

That is any path P has the form where there's an initial prefix,where

Â are the vertices are in x.

Â And then there's some first point at which it crosses the frontier and goes to

Â a vertex which is not an x, we're calling the first such vertex outside of x, z.

Â And then it can skip back and forth who knows, but

Â certainly it ends up in this vertex w* which is not an x.

Â So we're going to make use of just this minimal information about

Â an arbitrary path P.

Â And yet this will give us enough of a foothold to lower bound its length.

Â And this lower bound to be strong enough, we conclude that our path that we

Â computed is the best, smaller than any possible competitor.

Â 12:25

So let's just summarize where we left on the previous slide.

Â We established that every directed path from s to w* p,

Â no matter what it is has to have a prescribed form, where it ambles for

Â a while inside x and then the portal through which it escapes x for

Â the first time we're calling y.

Â And then the first vertex it sees outside of x is z and there has to be one.

Â And then it perhaps ambles further and eventually reaches w*.

Â It could well be that z and w* are exactly the same, that's totally fine for

Â this argument.

Â So here's one of our competitors, this path p and

Â I have to show it's at least as long as our path.

Â So we need a lower bound on the length of this arbitrary path from s to w*.

Â So let's get that lower bound by arguing about each piece separately, and

Â then invoking Dijkstra's greedy criterion.

Â So remember, we said we better use the hypothesis that edge links are non

Â negative, otherwise we're toast, otherwise we know the algorithm is not correct.

Â So here's where we use it.

Â This final part of the path from z to w*,

Â if it's not empty then it's gotta have non negative length right.

Â Every edge as part of this subpath has non negative edge length, so

Â the total length of this part of the path is non negative.

Â So y to z by construction is direct arc.

Â Remember, this is the first arc that path p uses to go from x to get outside of x.

Â So that's how it escapes, the conquer territory x and

Â this just has some length, l of yz.

Â 14:03

So that leaves the first part of this path,

Â the prefix of this path that lies entirely in capital X.

Â So how do we get a lower bound in the length of this path?

Â Well, let's begin with something trivial.

Â This is some path from s to y, so

Â certainly it's as least as long as a shortest path from s to y.

Â 14:24

And now, we're going to use the inductive hypothesis again.

Â So this vertex y, this is something we treated in a previous iteration.

Â This belongs to the set capital X, we've already processed it,

Â we've already computed our estimate of it's shortest path length, and

Â the inductive hypothesis assures us that we did it correctly.

Â So whatever value we have hanging out in our array capital A,

Â that is indeed the length of the true shortest path.

Â 14:49

So the length of the shortest sy path is l(y) by definition, and

Â it's A(y) by the inductive hypothesis, and now we're in business.

Â So what does this mean we can say about the total length of this arbitrary path P?

Â Well, we've broken it into three pieces and

Â we have a lower bound on the length for each of the three pieces.

Â Our lower bounds are, our computed shortest path distance to y,

Â the length of the direct edge from y to z and 0.

Â So adding those up, we get that the length of

Â path P is at least our computed shortest path

Â distance to y plus the length of the arc from y to z.

Â 15:39

So why is this useful?

Â Well, we've got one remaining trick up our sleeve.

Â There's a hypothesis which is presumably very important,

Â which we have not yet invoked.

Â And that is the choice of Dijkstra's greedy criterion

Â at no point in the proof yet have we used the facts that we select

Â which vertex to add next according to Dykstra's greedy score.

Â So that is going to be the final nail in the coffin,

Â that's what's going to complete the proof.

Â 16:33

And therefore in this iteration,

Â the edge yz was totally a candidate for us to use to enlarge our frontier.

Â Remember, we looked at all of the edges crossing from left to right.

Â Yz is one such edge and amongst all of them,

Â we chose the one with the smallest Dijkstra's greedy score.

Â That was the Dijkstra's greedy criterion.

Â 17:08

So this completes the proof.

Â So let me just remind you of all the ingredients,

Â in case you got lost along the way.

Â So what we started out with is we realized our algorithm or

Â Dijkstra's algorithm it does compute some path from s to w*.

Â It just takes the path it computed previously to v*, and

Â it just depends this final hop at the end.

Â So that gives us some path from s to w* moreover,

Â it was easy to figure out exactly what the length of that path is.

Â And the length of the path that we came up with is exactly the circled quantity at

Â the bottom of the slot.

Â It's the shortest path distance from s to v* plus

Â the length of the direct arc from v* to w*.

Â So that was how well we did.

Â But we had to ask the question, is it possible to do better?

Â We're trying to argue that our algorithm does the best possible,

Â that no competing path could possibly be shorter than ours.

Â So how did we do that?

Â Well, we considered an arbitrary competing path P.

Â The only thing we know about it is that it starts at s and it ends up at w*.

Â And we observe that any path can be decomposed into three pieces.

Â A prefix, a direct edge, and a suffix.

Â Then we give a lower bound on this path P.

Â The direct edge, the length is just whatever it is.

Â The suffix, we just use the trivial lower bound that's at least 0.

Â And that's where we use the hypothesis that every edge has non negative

Â edge length.

Â And for the prefix, because that's all in the stuff we already computed,

Â we can vote the inductive hypothesis and say, well whatever this path is,

Â it goes from s to come vertex and y.

Â So at least the shortest path distance from s to y which is

Â something we computed in a previous iteration.

Â We lower bounded the length of any other path in terms of the Dijkstra's greedy

Â score for that path.

Â Since we choose the path with the best greedy score,

Â that's why we wind up with the shortest path of them all, from s to w*.

Â This of course, is embedded in an outer proof by induction on the number of

Â iterations, but this is the inductive step, which justifies a single iteration.

Â Since we can justify every iteration giving correctness to the previous ones.

Â That means by induction, all of them are correct.

Â So all of the shortest paths are correct.

Â And that is why Dijkstra's algorithm correctly computes shortest paths and

Â any directed graph with non negative edge lengths.

Â