To put our, all our algorithms into
context and better understand them. What
we'll do now is go through some basic
properties. Of shortest paths in, edge
weighted directed graphs. So, what kind of
data structures are gonna need, first of
all? Our goal is to find the shortest path
from s to every other vertex. so, the
first observation is that there's gonna be
a shortest paths tree solution. well if no
two paths have the same length, then
certainly, it's gonna be, such a solution
and there's a number of ways to convince
yourself, that there's gonna be a tree. if
you've got two paths to the same vertex,
you can delete the last edge in one of
them and keep going until all that's left
is a tree, for example. So what we wanna
do is compute a tree. now, we've done
that, in several algorithms before. And a
reasonable way to represent the shortest
path's tree is to use two vertex indexed
arrays. the first one is for every vertex.
Compute the length of the shortest path
from s to that vertex. So in this case, we
have this shortest pastry, and we'll keep
the length from the shortest path from the
source, zero to each vertex. So zero two,
two, the length of that shortest path is
26. 027 two, seven, it's 0.60 and like
that. And so, because you go from zero to
2.36 and from two to 7.34 you get 60., and
so forth. And the other thing is, we've
done before is use parent link
representation, where edge 2V is gonna be
the last edge that takes us to V. And by
following back through that array, we can
get the path, as we have done several
times before. If we want the path from
zero to six, we go to edge 26 and says
well, the last thing we do is three to six
then we go to three and say the way we got
to three is from seven We go to seven say
the way we got to seven is from two We go
to two and say that's the way we got to
zero And if we put all those things on a
stack, then we can return them as an
noterable to the client and that gives the
edges on the shortest path. So that's the
data structures that we're going to use
for shortest paths. this is, actually the
code that does, what I just said. The
client query give me the distance, it
just, returns, uses v to index into the
instance array and returns the distance.
and if the client asks for the path, then
we make a stack and then, its variable e
is a directed edge, and we started edge
2v. And as long as it's not null, we push
it onto the path and then go to the edge
two entry for the vertex that we came from
and that gives the vertex that we came
from to get to that vertex and keep going
until we run out of vertices which happens
at the source. Then return to path and
that's iterable that gives the client the
path. So that's the implementation of the
two query method. So, now what we're want,
we're going to want to talk about for the
rest of the lecture is the algorithms that
build these data structures. Now, all of
the algorithms that we look at are based
on a concept called relaxation or edge
relaxation. So, now recall that our data
structure. So we're gonna talk about
relaxing an edge from v to w and we have
an example here, from v to w. and at the
point that we're gonna relax this edge.
we'll , have our data structures in
process in this too. We haven't seen all
edges. We haven't seen all passes, paths
in the intermediate part of some
algorithm. So, but we'll try to make sure
that this 2v for every vertex is the
length of the shortest known path to that
vertex. And that's gonna be the same for
W. So, these are all the edges that are in
Edge two that we know pass from some S to
some vertex. so this 2v and this 2w will
contain its shortest known path. Now, if
we in also Edge 2wv is the. Edge 2w is the
last edge in the shortest known path from
s to w. and the same way with extra v of
course. Now, so to relax along the edge
from v to w, essentially that means, let's
update the data structures to take that
edge to an, into account. And what happens
in this case is that the edge gives a
better way to get to w so that's what
relaxing is. that edge gives us a new
shortest pass so we want to include it in
the data structure. So since it has a
shorte r path, we have to update both,
disc 2w and edge 2Ww That is, we have a
new way to get to W. So we have to throw
away, throw away that old edge that came
to w and we have, a new shorter distance.
Instead of 7.2 that came that old way, we
have 4.4 that gets us, a new way. So edge
relaxation, is a very natural operation.
When we consider a new edge, does it give
a new shortest path to that vertex or not?
If it doesn't, we ignore it. If it does we
update the data structures to include that
edge and forget about the old edge that to
took us, took us to that vertex. That's
edge relaxation. And this is, easy
implementation of edge relaxation in code.
So to relax and edge. we pull out its
front and two vertices in VNW according to
our standard idiom, and then we just see
if the distance to w that's, what's the
shortest path before, is bigger than the
distance to v plus the weight of the edge
that would take us from v to w if it's
bigger, that means we've found a new path.
If it's less than or equal we ignore it.
And if we found a new path we have to
update the distance to w to be the new
distance. Distance to v plus follow VW.
And then we have to update edge 2w and
throw away the old version and say that
our new edge from v to w is the best path
to w as far as we know. So that's easy
code for edge relaxation. Now we're gonna
use edge relaxation in a really
fundamental way to compute shortest paths,
but there's one other important idea which
is called optimality conditions, and this
is a way to know that we have shortest
paths, and we have computed all the
shortest paths, so the shortest path,
optimality conditions, are is embodied in
the, in this proposition, so we have an
edge way to diagraph. and we have the this
two array. Let's just talk about the
distances and path go with the distances.
But the key point is that this two array
represents the shortest path distances
from the given source s, if and only if
these two conditions hold. So the first
thing is, if its the length for every
vertex, this 2v is the length of some path
from s to the vertex, and our algorithm
always try to ensure, will, always ensures
that. And then, the second thing is for
every edge, vw We have this condition
that, that this 2w that we, have stored is
less than or equal to this 2v, plus the
weight at the edge from v to w. That's the
shortest path optimality conditions. if,
they're equal, So sometimes, they'll be
equal. for example, if vw is the last edge
on the shortest path. and sometimes, it
would be great if it, it, never been
smaller, and never be way to get the W
that we haven't found. That's the shortest
path, optimality conditions. and again,
just a quick proof although best way to
understand proof is that we've been slowly
now listen to them, spoken quickly, but
I'll quickly outline them. so here is the,
the necessary suppose that so, so we wanna
prove that if, if this is true then we
have shortest paths. So to do that we
assume the contrary. Suppose that the
distance to w is bigger than the distance
to b + e that way for some edge. Then that
path is gonna give a path to w that's
shorter than distance w cause v is the
path and the wait's shorter. in that is a
contradiction to the idea that you have
shortest paths so there can't be any, such
edge where that condition holds. so that's
necessary and then sufficient. Suppose
that we have shortest path from s to w.
then Now we're assuming these conditions
all hold. then, For every edge on the path
this has to all hold. so, so, for, it
starts at the end. so, the distance to the
last edge goes from VK - one to VK. So
distance to VK is less than or equal to
the distance to VK - one plus the weight
of the Kth edge. and so just continuing
down that way then from the source to the
first edge, but it's a source plus the
weight of the first edge is greater or
equal distance to the first vertex after
the source, and all those conditions have
to old. And then, what we can do is just
add up all those weights. and simplify it.
But and then that shows that the distance
to w is equal to the length of the
shortest path. an d so it's gotta be the
weight of the shortest path. Because it's
the weight of some path and it's got that
weight, it's gotta be the weight of the
shortest path. so if those conditions hold
we have shortest paths. So our the, the
point of this proof, it's a slightly
complicated proof, but it's not too bad,
it's quite natural is that all we have to
know to w-, check that we have computed
shortest path. These are these optimality
conditions hold, to prove that an
algorithm computes shortest paths. We just
have to prove that it ends up with the
optimality conditions and force, and
that's what we'll be doing. And the
optimality condition, really, it's just
saying that there's no edge there that we
missed. Okay so with that idea, in fact
there's a very simple, easy to state,
generic algorithm that is going to compute
shortest paths. and it's very simple. We
start with the distance to the source
being zero And the distance to every other
vertex infinity. And all we do is repeat
until the optimality conditions are
satisfied, relax any edge. Just go ahead
and relax edges until the optimality
conditions are satisfied. So, That's a
very general algorithm. We don't say how
to decide which edge to, relax or how to
know the optimality conditions are
satisfied. But still, it's, quite an
amazingly simple generic algorithm. so,
how do we know, how can we show that it
computes the SBT? Well it's pretty simple.
throughout the algorithm. We're making
sure that because of the way that we do
relax edges the distance to V is the
length of a simple path from S to V, and
edge s to v is the length of a simple path
from s to v and edge to v is the last edge
on that path That's what relaxation does
for any vertex that we touch. and not only
that, every relaxation that succeeds
decreases the distances. and we've assumed
that there's a way to get to every, every
vertex. and there's only a finite number
for paths. So it can decrease, at most, a
finite number of times. So it's going to,
the algorithm's gonna terminate. It's as
simple as that. A gain, this is a little
bit of a mind blowing concept. But we'll
leave that for more careful study and just
for now realize that all we have to do is
relax along edges. And what we're going to
do now is look at. Different ways of
figuring out how to choose which edge to
relax. The first algorithm that we'll look
at is a classic algorithm known as
Dijkstra's algorithm one of the most
famous of all algorithms. and that is
effective when the weights are non
negative. then we'll look at an algorithm
that works even with negative weights as
long as there aren't any directed cycles.
and then we'll look at an even older
algorithm than Dykstra's, the Bellman-Ford
algorithm. that can, solve the shortest
path, problem and graphs with negative
weights, as long as there's, no negative