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.