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.