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.