In this video I'll prove to you that Dijkstra's algorithm does indeed compute
correct shortest paths in any directed graph where all edge lengths are
nonnegative. Let me remind you about what is Dijkstra's algorithm. It's very much in
the spirit of our graph search primitives, in particular, breadth 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 zero, and the shortest
path from S to itself is the empty path. So then we'll have a main [inaudible]
loop. There's gonna be N minus one iterations. In each iteration, we'll bring
one vertex which is not currently in X into capital X. And the variant we're
going to maintain is that all the vertices in X we would have computed estimates of
the shortest path distance from s to that vertex, and also will have computed the
shortest path itself from s to that vertex. Remember our standing assumption
stated in the previous video, we're always gonna assume there's at least one path
from the source vertex s to every other destination v. Our job is just going to
compute the shortest one, and also we have to assume that the edge lengths 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 tail is 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. Now, there
may be many such edges. How do we decide amongst them? Well, we compute the
Dijkstra greedy score for each. The Dijkstra greedy score is defined as the
shortest path distance we computed for the tail. And tha t's been previously computed
cuz the tails in capital X. And then we add to that the length contributed by this
edge itself, by the edge (v, w), which is crossing the cut from Left to right. So
amongst all edges crossing 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 star W star for the purposes of notation. W star is the one that gets
added to X, so it's the head of the arc with the smallest greedy score, and we
compute the shortest path distance of that new vertex W star to the be the shortest
path distance to V star plus the length contributed by this edge V star W star and
what is the shortest path. It's just the shortest path previously computed to V
star, plus, this extra edge V star, W star, tacked on to the end, Is the formal
statement we are going to prove. For this video we're not going to worry at all
about running time. That will be the discussion of the next video. We'll
discuss both the running time of the basic algorithm and a super fast implementation
that uses the heat data structure. For now we're gonna just focus on correctness. So
the claim is that for every directed graph, not just the 4-node, 5-arc example
we studied, as long as there's no negative edge lengths, Dijkstra's algorithm works
perfectly, computes all of 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 of
v. Is exactly the correct shortest path distance, which we were denoting by
capital L and V in the previous video. So both the algorithm and the proof of
correctness was established by Edsger Dijkstra, this is back in the late 1950s.
Edsger Dijkstra was a Dutch computer scientists and certainly you know, one of
the forefathers of the field as a, as a, as really as a science, as an intellectual
discipline. He was awarded the ACM Turing award, that is the Nobel prize in computer
sci ence, effectively, I believe it was 1972 and he worked for a long time in the
Netherlands but also spend a lot of his later career at UT Austin. So the way this
proof is gonna go is by induction. And basically what we're going to do is we're
going to say every iteration when we have to commit to a shortest path distance to
some new vertex, we do it correctly. And so then the form of the induction will be,
well that given that we've 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 induction,
the base case is completely trivial. So that just says before we start the while
loop, what do we do? Well, we commit to the shortest path distance from s to
itself. We set it to zero. 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
nonempty path can't get you negative edge length better than zero. So the first
shortest path computation we do from S to S is trivially correct. The hard part, of
course, is the inductive step justifying all of the future decisions [inaudible]
done by the algorithm. And of course, mindful of that example, that non 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, okay? Otherwise,
the theorem would be false. So we'd better, somewhere in the proof, use the
fact that edges cannot be negative. So let's move on to the inductive step.
Remember the inductive step the first thing to do is to state the inductive
hypothesis. You're assuming you haven't made any mistakes up to this point. Let's
be a little bit more formal about that. So that is everything we computed in the past
okay 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 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 capitol X. What we computed as our estimate of the
shortest path distance for V is in fact the real shortest path distance. And also.
The computed shortest path. Is in fact a true shortest path from STV. 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. So what happens in an iteration? Well, we
pick an edge, which we've been calling (V star, W star). And we add the head of this
edge W star to the set X So let's get our bearings and remember what Dijkstra's
algorithm computes as the shortest path and shortest path distance for this new
vertex W star. So by the definition of the algorithm, we assign as a shortest path.
Reported shortest path from S to W star. The previously computed reportedly
shortest path from S to V star. And then we tack on the ends the direct arc V star
W star. So pictorially we already had some path that started at S and ended up at V
star and then we tack on the ends this arc going to W star in one hop. And this whole
sha-bang, is what we're going to assign as, Paw star. So let's use the inductive
hypothesis. The hypothesis says that all previous iterations are correct. So that
is, any shortest path we computed in a previous iteration is in fact, a bona fide
shortest path from the source s to that vertex. Now, V star, remember, is in X, So
that was previously computed. So, by the inductive hypothesis, this path BV star,
from S to V star, is in fact a true shortest path from s to V star in the
graph. So therefore. It has length L of E star. Remember, L of E star is just, by
definition, the true shortest path distance in the g raph from S to V star.
And now, given that the path that we've exhibited from S to W star is just the
same one as we inherited the V star, plus this extra edge tacked on. It's pretty
obvious what the length of the left hand side is, So it has length. Just the length
of the old path, which we just argued is the shortest path distance from S to V
star, plus the length of this arc that we tacked on. So that's gonna be L of V star,
W star. So by the definition of the algorithm, what we compute for W star is
just [inaudible] score which is just the computed shortest path distance to the
tail. V star plus the length of the direct edge, by the inductive hypothesis we've
correctly computed all previous shortest path distances. V star is something we've
computed in the past by conductive hypothesis is correct so this is equal to
L of V star. By the inductive hypothesis. Alright. So don't worry if you're feeling
a little lost at this point. We 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? Well first of all our estimate of the shortest path
distance from the source to W star to the new vertex that we're including in the
[inaudible] X is the true shortest path distance to V star, plus the length of the
edge from V star to W star. That's the first thing. Secondly, the path that we
have in the B array. Is a bonified path from S. To W. Star with exactly this
distance. 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 Dijkstra's algorithm. So what do
we need to prove? We need to prove that this isn't just any old path that we've
exhibited from s to this vertex W star. That it's the shortest path of them all.
But differently, we need to show that every other s W star path in this graph
has length at least this circled value. So let's proceed. Let's show that no matter
how you get from the source vertex S. To this destination W. Star, the total length
of the path that you travel is going to be at least this circled value, At least L Of
V Star, plus L Of V Star, W Star. 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 star. 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 starts exactly at the head of the edge we chose in this
iteration, So this is not an X. So any path that starts in X and goes outside of
X, at some point it crosses from one to the other. So let's think about the graph
and its two pieces, that to the left of the frontier and to the right, the stuff
is already processed and the stuff that, which has not yet been processed. S, of
course, is in the left hand side. And at the beginning of this iteration of the
while loop, W star was on the right hand side. Any path, no matter how wacky, has
to at some point cross this frontier. Maybe it does it a bunch of times, who
knows. But it's gotta do it once. Let's focus on the first time it crosses the
frontier, and let's say that. It crosses the fronts here with the vertex Y going to
the vertex z. That is, any path p has the form where there's an initial prefix,
where all 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 I can skip back and forth, who knows,
but certainly it ends up in the vertex W star, which is not in X. So we're gonna
make use of just this minimal information about arbitrary path p, and yet this will
give us enough of a foothold to lower bound its length, and this lower bound
will be strong enough that we can conclude that our path, that we computed, is the
best. Smaller than any possible competitor. So let's just summarize where
we left off on the previous slide. We established that every directed path from
S to W star P [sound]. No matter what it is it has to have a prescribed form. Where
it ambles for awhile 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. Star. It could well be that Z and W star were exactly the same that's
totally fine for this argument. So here's one of our competitors this path P and it
shows it's least as long as our path. So we need a lower bound on the link of this
arbitrary path from S to W star. So, it's get that lower bound by arguing it by each
piece separately and then invoking Dijkstra's greeting criterion. So remember
we said we better use the hypothesis that edge links are non negative otherwise we
are toast, otherwise we know that the algorithm is not correct. So here's where
we use it. This final part of the. Path from Z to W star. If it's nonempty, then
it's gotta have nonnegative length. Right? Every edge, as part of this subpath, has
nonnegative edge length. So, total length of this part of the path is nonnegative.
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. Okay? So it's how it escapes, the
conquered territory X. And this just has some length L Of YZ, So that leaves the
first part of this path the prefix of the path that lies entirely in capital X, so
how do we get a lower bound on the length to this path. Well, let's begin with some
trivial, this is some path from S to Y so certainly it's at least as long as a
shortest path from S to Y. And now we're gonna use the inductive hypothesis again.
So this vertex Y, this is somet hing we treated in a previous iteration, right?
This belongs to the set capital X. We've already processed it. We've already
computed or estimated the 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 a true shortest path. So the length of
the shortest SY path is L of Y by definition. And it's a Y by the inductive
hypothesis. And now we're in busy. Alright, 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 link 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 zero. 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
arch from Y to z. So why is this useful? Well, we've got one remaining trick up our
sleeve. Is a hypothesis which is presumably very important, which I 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 fact that we select which vertex to add next
according to Dijkstra's greedy score. So that is gonna be the final nail in the
coffin, that is going to complete the proof. How do we do that? Well, we've
taken an arbitrary path p. We've lower bounded its length in terms of the
computed shortest path distance up to the last vertex of this prefix y, plus the arc
length to get from X to outside of X, C(y,Z). So, remember this means Y is in
the left part. Of the frontier and Z is not 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-greedy score. That
was the Dijkstra-greedy criterion. So what have we shown? We've shown that th e
length of our path. Is no more then what's a lower bound on the length of this
arbitrary other path p. 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 star, right. It just takes the path it computed previously to V
star and it just appends this final hop at the end. So that gives us some end from S
to W star. 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. Comma
apostrophe star [inaudible], plus the length of the direct arc from V star to W
star. So that was how well we did. But we had to ask the question, is it possible to
do better? Well, we're trying 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 ends at the W star 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, right? The direct edge, you know the length is just
whatever it is, the suffix we just use the trivial lower bound that will be zero 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
invoke the inductive hypothesis and say, well whatever this path is, it goes from S
to some vertex in 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 greedy score for that path, since we
choose the path with the best Greedy score. That's why we end up, we wind up
with the shortest path of them all from S to W star. This, of course, is embedded in
a 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 given
correctness of 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. Any directed graph with
non-negative edge links.