In today's lecture, we're going to be looking at paths between
points in a graph between vertices and a graph. And our goal is
to try to find the shortest route between any two vertices.
So this is a very natural question and it comes up in some pretty
familiar settings. So, for example, whether you've ever wondered
how your satnav works. See, when you get in the car and
you programme your Saturn, I have to find the shortest route between, say, Oxford and,
I don't know, Cambridge. Then how does it do it?
Well, obviously, it has stored in its memory a graph which represents
the road network of the UK. And each graph,
each edge of the graph has a length associated
to it, which may be is the amount of time that you can travel along that road, how long
it takes to travel along that road. And so
what the Saturn does not do is it does not go through every possible route
from Oxford to Cambridge. There are just far too many of them for it to be
able to do that. Instead, it turns out that there is an efficient
algorithm for finding the shortest route between two vertices.
And that's what I'm gonna be describing today. So the setup
is very natural, I think. You start off with G a
connected graph. Say this one here. And
each edge has been assigned a positive length L of a.
And so once you've assigned lengths to edges, it makes sense to talk about the length
of paths. So the L length of a path P is just
some of the lengths of it. Such as? So we use the terminology
whole length rather than length, because we've already used,
already defined what we mean by the length of a path. It's just the number of edges in that path.
But we obviously want to have a notion which takes account of this function
l assign, which assigns to each edge a positive real number.
So that's what we talk about, the L length. But because the length is a bit of a mouthful
in today's lecture, whenever I say length, I mean a length.
OK, so. What we're interested in is
how shortest paths between two vertices, X and Y. So
an L shortest X Y path is by definition an X Y path
that minimises the length. And it's not at all obvious
how to find that. So, for example, in this example of these two vertices,
X and Y. The most efficient route to get from
one to the other is not to go along this edge here because that has length for in
fact, the most efficient route is to take this this red path
here, because that has length three.
So dextrous algorithm is what we're gonna be describing today
and what it does is it for any two vertices, X and Y,
it finds an El shortest X Y path.
So the idea is that we think of X as fixed in some sense
and we're going to think about all possible vertices Y.
Well, the algorithm does is it maintains
a tentative distance from X.
Called DeeVee for each Vertex V of the graph.
So DV is going to change
as the algorithm progresses.
D of any Vertex V can be a non negative real number, or it can
actually be infinity as well.
So this function D from the vertex sets to
the real's together with infinity. It's important to realise that this
is going to change as the algorithm progresses.
But at each step of the algorithm, we finalised deal view for some Vertex
U. After that, it won't change. By the end of the
algorithm, we've finalised of view for all of the vertices you
and it'll be equal to the correct value, namely D of you
will be L of P star of you, where P star view is
some L shortest X you path.
OK. So that's the way that the algorithm is going to work.
So. What the algorithm does is it keeps
track of a subset you of the vertex set.
So initially you is the entire vertex at. So you
is the set of vertices for which DeeVee has not yet
been finalised. So in other words, you you should think of
as the as the set of uncertain vertices, ones
that we're not yet sure of for what the final deal value of that
vertex should be. So initially,
you is the entire vertex set. So we're not sure
of the value of any vertex in our graph.
Rhythm starts with D. value of the base vertex
to be zero and. Value of every other vertex
to be infinite. Then what does it do?
It keeps on repeating the following step. If you
is empty, we stop. That means that there are no vertices
with uncertainty value. We finalised the devalue
of all vertices. In other words, so we could stop.
Otherwise, we pick some Vertex U in U for which
D. U is minimal. Then what we do is we
delete you from U. And in
other words, we finalise. The devalue view,
and we also do the following. For any Vertex V in U
with V adjacent to U. And satisfying this inequality.
Namely, that DV is strictly greater than deserve of you. Plus
the length of the Yuva edge. If that's the case, we replace
T V by D of you plus L. Of U. V.
So, in other words, that has reduced the deep value of that Vertex
V. OK. So
it might not be obvious. What the algorithm is doing, it's really best
to look at an example to start to get a feel for how this algorithm works.
So here's an example. Here's our example. Here is
our graph with the lengths assigned to its edges
and his of text X. And, um,
I have a label. I've met coloured all of the vertices red
because they're in our set you of vertices for which
the D value is not yet certain.
So initially we set D of X to
be zero and D of all of these other vertices to be infinite.
OK, so the first stage is to peg the vertex
with smallest devalue. That's X in this case,
it is always X and we remove it from you. In other words,
we finalises, devalue. And
what we do is for every Vertex V adjacent to you.
And satisfying DSV is greater than deserve you. Plus al Newfie.
We replace TAFE by D of you. Plus l u v.
So in other words, we should go through each of these vertices that are adjacent to
this Vertex X. And we ask ourselves, is its current
devalue? Greater than the deep value of X.
Plus, the length of that edge. Joining ex to that vertex.
Well, in this case, the answer is definitely yes, because this is infinite here and D
of X plus one is definitely strictly less than infinity. So we should
replace that vertex, the value of that vertex by one.
And similarly, we should replace the T value of this vertex by three, this one by four, and this one
by one. OK, so we've done the first step of the algorithm.
Let's continue. Now we have to pick a
vertex in you. In other words, one of these red vertices with minimal devalue.
There are two of them. There's this one down the bottom and there's this one on the top. Let's pick the one on the bottom.
So we finalise its devalue. That means we remove it from the set you.
So it's not that vertex is no longer red. And then we look at
all of its neighbours that are in you in this case,
there's just the one of them. This vertex here and we ask ourselves,
is the devalue of that Vertex V strictly greater than the D value
of you? Plus the length of the edge u. V. Yes, it is,
because three is greater than one plus one. So we should replace this three
by a two. Now we continue.
So the again, we look at the vertex with smallest devalue
is this one on the top. So we finalise that and then we look at all of its neighbours
and we ask ourselves, is the deep value of this case?
All of its neighbours knew this. This is just one of them. Is that devalue
strictly greater than the value of you? Plus the length of that edge?
Well, in this case, four is less than one plus five. So we don't change
that. OK, so now
we look at the next one here, this is the next vertex that we
this is the next vertex and you with smaller Steve. We finalised that one.
We look at all of its neighbours in you, that's just this one. And
we say, should we be decreasing their devalue? Well, in this case,
we should, because four is greater than two plus one. So we should
reduce that to three. Now it comes the final step of the algorithm.
This is the last vertex, and we finalise its value and we stop.
And as you can see, the values on these vertices really
are correct. They do represent the length of the shortest path.
The L length of the shortest path from X to that vertex.
So, for example, we saw that the shortest path from X to this vertex here
was going around the edges with length one.
And so that the that the correct devalue there
is indeed three. OK. So it's done
the correct job. In fact,
the extras algorithm can be used to do more.
What it can do is it can be used for
any vertex acts to construct a spanning treaty
with the following property. If any vertex Y
in the graph. The unique x y path
in T is actually the shortest and L
shortest x y path, so it's quite
surprising in my view, that such a tree should exist.
We call such a treaty an El shortest paths tree rooted
at X. So let me give you an example. I've highlighted here
in red. Such a shortest paths tree.
And you can easily cheque that the shortest way of guessing from any vertex
to X is to go via the edges in this tree.
So that is what the shortest paths tree that that's is defining property, that the shortest
way of getting from any vertex to acts is to follow the unique path in
the tree from that vertex to X.
OK. So how come we had what it takes just algorithm to how does it
create this tree? So we're going to describe
how to obtain the tree tea. OK,
so here's our example that we're looking at. So what it does
is for each vertex v. other than the base Vertex X.
We define its parent. So the parent of
a Vertex V. Is the last vertex
you. With a property that we replaced, a V
by D of U plus L u v during the algorithm.
So if you remember, for every vertex. We kept this tentative
notion of distance D from X.
And this deal, as the algorithm progressed, kept on going down.
And at some point, it stops. Now,
when it goes down. What? The way that it goes down is that
Davey is goes down. So the value of you plus l
u v for some vertex you. And
so when it goes down for the last time that you is called the parent
of the. So, for example, in this case here, when we ran the
algorithm, we we first of all finalised X
and then we finalised V, this Vertex V here. And
before we finalised it, we reduced the D value of V by
saying that it was the D value of X plus the length of this edge. So in
other words, X is the parent of V K, so I've drawn in in read
the parent to V. The next stage
of the algorithm was to finalise this vertex here
that had its value, had gone down from infinity to one. And when it went down
from infinity to one, that was because it was equal to the deep value of
X plus the length of that edge. So the parents of this vertex here
is also X. The parents of this vertex here is this
vertex B and so on. And so what we do is we create
our tree. So we obtain our treaty. By
drawing an edge from each Vertex V. Other
than X. To its parent.
OK, so this is the algorithm, and it's not at all
clear that it does the right job. And in fact, I'm gonna be spending
the rest of the lecture explaining why the algorithm does
book. So I
want to start by proving Alema, which she's going to give us some
structural results about. Te. And about
de. So it has two parts to it. The first
part of the Lemmer is that T is indeed a tree.
It's clearly, therefore, spanning tree. Because if you remember, the way it was defined was
for every vertex other than X, there was an edge going
from that vertex to its parent. So in other words,
this really does cover every single vertex of the graph.
So once we've proved this, Lemmer proves that it's a tree will have the tea is a spanning tree.
But we won't yet prove that it's the shortest paths spanning tree.
Instead, what we'll do is prove the following.
For each. Vertex, you. Do
you view will show is equal to the length of pay,
if you pay, if you is the unique X, you pass in T.
So that'll be clearly a useful thing to do. So the final thing that we claim
is that the shortest way of getting from you to X
is by following this path. This unique path p
u. So we haven't proved that. And this lemma isn't claiming that yet. But
what is claiming is the D of U is the length of that path.
P u in T. OK,
so let's prove this lemme.
So at each step. We have a subset.
You and can, let's see, be
the complement of you, so see is the set
of vertices for which the D value is certain. That's what's
called C. It's been finalised. Those are the vertices which is finalised.
And suddenly the case for every finalised vertex with finalised
devalue. We know what its parent is. Because
we know the last time that we decrease that devalue, and hence we know
what the parent of that vertex is, so we can certainly have defined
the parents of all the vertices in see.
OK, so let me just run through this algorithm again, in this particular case,
keeping track of the red vertices, which are the ones
for which we're not yet certain. So as we run
through the algorithm, you can see that the black vertices,
one complement of you, is growing.
So that's those are the vertices and see.
So let TFC be obtained by drawing an edge
from each vertex. In C minus six to its parent.
So V, T.C., his C. So here's an example. For example,
we're halfway through the algorithm here. What we've done is
we've finalised the deep value of X and we finalised
the value of this vertex here. So see consists
of these two vertices and you is the remaining vertices.
And more so because we finalised the value of this bottom vertex,
we know what its parent is. We know that it's X. And
so we defined T.C., which is the
fact that the graph, which is obtained by going through every single vertex
in sea other than the base vertex. And adding
in the edge, which goes from that vertex to its parent.
So V of T, c, c.
The next stage, for example, we've enlarged see
and that, by and large, TFC.
And so on and so forth. So you can see that what we're doing
is we're gradually building tea. We're just adding in the edges of
tea. One by one. And at any given stage,
we've got this craft, T.S. So what we can do is we're going to
show by induction on the number of cardinality of C,
the T C is a tree. And for each vertex
you have TSC. In other words, each you in, see? We have that
day of U is L of pay off here.
In other words, the length of the unique X you pass in
T.S. So that will clearly do the job. So the
way this is working is we're building up a T. One
edge at a time. And as we're going along, we're proving
what we need to for just the
vertices in C. So by the time
that the process is finished and C is everything
will have proved Alema. OK,
so that's just a restatement of what I wrote down before, we're going to show by induction
on the cardinality of C. The tacy is a tree.
And for each vertex, you, A.C. and otherwise, each you in see,
we have the D of you is L of P u.
OK, so the base case is pretty straightforward.
The very start in cases where the vertex set of TCE is X.
As just a single vertex Senate, no edges. It's definitely a tree. And
D, if that Vertex X is the correct value, it's zero, which is L of P
X. OK, so now we're going to the
induction step. So I suppose we've got to this stage
here. We're now going to add in one more
element to see. We're going to finalise one more, the devalue of one more vertex.
So the next one, next vertex we're going to finalise is this vertex
you it's the one for which T is minimal in you.
When we do that, we delete you from our set.
But you have to seise that for which the devalue is uncertain and thereby we
add it to see. And we add
an edge you, which joins you to its parent,
which lies inside, see? So in other words, we add
we know by induction that the inductive hypothesis is that
what we've created in green so far, T.C., is a tree.
And what we're doing is we're adding a leaf to that tree. And so it stays a tree.
OK, so that's one part of the thing that we have to show that each
time we add an edged T.C. staes tree.
We also need to cheque that when we add in this vertex, you.
Day of U is L of pay if you.
OK, so what is D of you? Well, D of you remember,
he's been going down on the very last time, went down. We set it equal
to DSV plus L v you. For some Vertex
V, which by definition is the parent.
So Day of U is equal to D.V. plus L. V you for V
the parent view. The lies inside
see, and so by the inductive hypothesis, DV is
equal to the length of the path, unique path
in the tree. Joining V to X i.e. A
so deep V is how Peevey.
But out of PVA plus, our view is the length of pay you
because the unique path in the tree joining you to X.
We use it a leaf of the tree, so it travels along
U. V. And then it does. Peevey did.
And so I've shown what I needed to show, namely that for this new vertex
deal of you is equal to L. P.
And so I'm done by induction.
OK, so what have we got to. Well.
We've been building this tree tea and we now know that tea is a tree.
And we also know that for every vertex. It's
devalue is equal to the length in the tree.
From that vertex to X. But what we need to show
is that actually the devalue is equal to the.
The shortest possible route in the whole graph from that vertex tax.
In other words, we've got to show that there is no
quicker way of getting from that vertex to X other than going by the tree.
T. So in other words, what we've got to show, and this will complete the proof
that the algorithm works. We're going to show that T is
an L shortest paths tree rooted ATEX.
OK, so we've defined D of you. I'm going to define
D star of you as follows. So if each vertex you in
Beijing D star of you is L of peace,
star of you for some L shortest x you path p
star you. OK, so it makes
sense to consider this quantity we call our quantity D. If you.
And we want to prove that it's equal to
the length of the shortest path from you to X. So we've defined
this DENR of you to be the actual length of the shortest path from
you to Axe. So we want to show that day of you. His teacher,
Dorothy. So we're going to show by induction that each step of the algorithm
when you. Is deleted. We have D of you is equal to D Starkie.
And so we'll be done.
OK, so the base case is. So we're we're inducting, obviously,
on the cardinality of C.
So the base case is when we have just a single vertex,
namely when you is X, well, D of you. Is that
the final value of D of you? I mean, delete it from from U u
equals X zero. And that's the correct value,
namely the the length of the shortest path from X. X has zero.
OK, so that's the base case. What about the inductive
step? OK, so.
What we're trying to show is the day of you is DENR of you,
every vertex, you join that one vertex. This time we do it considering the vertex
where we delete you from our set here. In other words, when we finalise the value
of D. Well, clearly, de.
Star of you is less than or equal to D of you.
Why is that D star if you. Is the length of the shortest path from you to
X? And we've shown that dear view is the length of the shortest
path from you to X in the tree. So therefore,
Daystar you is definitely less than or equal to D.F. you.
So the only way they could fail to be equal is if the inequality was strict. So I suppose
for contradiction, the day of you is strictly greater than de star.
If you. OK.
As usual. Let's see. Viji minus you. These are the vertices that we have finalised.
And we know that. So we're proving that as we
finalise each vertex. D If that vertex is t star of that vertex.
So for the vertices that we finalised, know every Vertex V in
our treaty C. We know that D star of his TV.
OK. So the setup is something a bit like this. This is some
graph. This is my base, Vertex X.
And so you so so did these these vertices in green that the vertices
and see, they are the ones whose deep value has been finalised.
And also in green is the tree, T.C.
And what we're doing now is we've finalised some new vertex you.
So you is the vertex who's devalue, we're now just finalising. So this is the
stage we're at in the algorithm. And what we want to do
is we want to show the deeds of you is equal to these star.
And we're assuming for a contradiction that do you view is strictly greater
than dystrophy. OK. So
we have peace star of you. This is the length of the shortest path.
In the graph from X to U.
So it clearly starts at X.
Which is in SI. And it ends in
our set you. And so there is some first point
when it leaves. See? So let y y primed
be the first edge of this shortest path p style you.
With why not in you? In other words, why in C? But why primed
in, you know, this is our first time, this pasto, you leaves
the tree. It could actually happen that it's the
that it ends at you. That's completely fine, but it might not.
OK, so we're going to focus on this edge y y primed.
Now, by induction, we know that that
all of the vertices in this tree, T.S.
They have the correct devalue, namely D of Y is equal
to D star of Y particular for this vertex y.
OK, so now we have a sequence of inequalities. Some of them are more obvious than
others. The first one is possibly the least
obvious. I claim that day of why primed is
less than or equal to D of y plus l. Y. Y primed.
OK, so the first inequality is because of the the update rule.
So. What it does is.
Each time we put a vertex into C, we finalise it.
What we do is we look at all of its neighbours in you. And we say.
Is there D value greater than D of this vertex Y
plus the length of the edge? So when we finalised
the deal value of Y. We would have done this for
this edge here, so we would have looked at the deep value for why primed and we would have said.
Is it strictly greater than the value of Y plus l.
Y y. Primed. And if it was, we would have
decreased the T value of Y prime down to that value.
Well, maybe at later steps in the algorithm, the devalue of why Prime went down even further.
But that's fine. We get the inequality that day of why primed is less than or equal to
deserve. Why? Plus l y y primed.
OK. Next pit is fairly obvious. We've already shown that
because of the induction hypothesis, D of Y is equal to D staff Y. So
these two are equal. And by definition.
D staff. Why is L of P star, why the shortest possible
path from Y to X?
And I claim that L. Of Peace star Y plus l y y
primed is less than or equal to Hall of Peace star you.
So why is that? OK, so peace star, you
is a shortest path between X
and you. So that means that any sub path of
it also has to be a shortest path. Joining two
versus the two ends of that path. Otherwise, there would be a way
of shortening peacetime. You.
So that means that the. Shortest
way of getting from Y to X. It's to go fire
peacetime you. So
that means that L. Of P star, why
shortest way? Plus, the length of why
why primed? Well, that's the total length
of this sub path from X to Y primed.
That's a subset of the entire of peace star you. And so we get the inequality.
Hell of peace star y plus l y y y pride is less
trinkle to l p start you.
OK. So al of peace star you is by definition
and de star, if you that's what how these stars defined it's.
It's the shortest possible length, the shortest possible path from you to
X. And we're assuming that piece W is such path.
And remember, we were supposing for a contradiction
that Daystar Star, you was strictly less than de if you.
So putting all these together, we get that the deep value
of Y primed. He's strictly less than the devalue.
You.
And that is a contradiction. So why?
If you remember, the way the algorithm works is
it chooses to finalise the default. You. Of a vertex
in our set you with smallest possible D.
And we're supposing that it's finalising this vertex you.
But it shouldn't have done because the devalue of Y primed is strictly
less than it. That's what we just proved. And so, in other words, it should
have. Instead of finalising the value of you, it should have finalised
the T value of Y primed. Or some other vertex with even smaller T value.
That is a new. So that's a contradiction that contradicts her choice of U.
And so what is what what what what hypothesis
is that contradicts then? So that contradicts the hypothesis that that
Daystar view was strictly less than did you.
So we did use the D of view is actually equal to D. Starr, if you. And that is what we
needed to prove. So that completes
the proof of the theorem that T is an
L shortest path, tree rooted attacks.
And therefore, that completes the proof that dextrous algorithm
works. Something is quite a remarkable algorithm
because it's extremely efficient. Let's just analyse its running
time. So the running time of this algorithm is
is big. Oh. Of the number of vertices of the graph times, the number
of edges in the graph. So let's just understand why that is.
Well, at each stage, what we're doing is we are
finalising the deep value of a lot
of other vertex. So we're running through each of the vertices
one by one. So the number of steps
his we do that is his of the the
number of vertices. But what do we do at each stage?
Well, for that given vertex, we look at
all of its neighbours and we
possibly reduce their T values. Well, how many neighbours does that
vertex have? Well, certainly at most the number of edges in the graph.
So. The number of devalues that it needs to change at any
given stage is the most the the the number of edges in the graph. And so
the total running time is equal to most the number of vertices times,
the number of hedges. In fact, Ashley,
you can slightly rearrange takes his album somewhat using slightly
better implementation, which we emit, which gives her a better running time, which is where
the number we were at, which is Bego, of the number of edges, plus the number
of vertices times log of the number of vertices. But in any
case, the version of the algorithm that I described here really is
very efficient. It's bounded above by
a polynomial in the number of vertices and the number of edges. And that is
what we're taking is a working definition of efficient. In particular,
it's much, much more efficient than the naive algorithm of
just looking at all possible paths between a pair of vertices.
Looking at the length of each and just taking the minimum that that takes far,
far too. OK, so that completes this lecture.