1 00:00:12,440 --> 00:00:17,840 In today's lecture, we're going to be looking at paths between 2 00:00:17,840 --> 00:00:22,850 points in a graph between vertices and a graph. And our goal is 3 00:00:22,850 --> 00:00:29,850 to try to find the shortest route between any two vertices. 4 00:00:29,850 --> 00:00:34,980 So this is a very natural question and it comes up in some pretty 5 00:00:34,980 --> 00:00:40,170 familiar settings. So, for example, whether you've ever wondered 6 00:00:40,170 --> 00:00:45,450 how your satnav works. See, when you get in the car and 7 00:00:45,450 --> 00:00:51,120 you programme your Saturn, I have to find the shortest route between, say, Oxford and, 8 00:00:51,120 --> 00:00:56,580 I don't know, Cambridge. Then how does it do it? 9 00:00:56,580 --> 00:01:01,710 Well, obviously, it has stored in its memory a graph which represents 10 00:01:01,710 --> 00:01:07,530 the road network of the UK. And each graph, 11 00:01:07,530 --> 00:01:12,690 each edge of the graph has a length associated 12 00:01:12,690 --> 00:01:17,790 to it, which may be is the amount of time that you can travel along that road, how long 13 00:01:17,790 --> 00:01:23,760 it takes to travel along that road. And so 14 00:01:23,760 --> 00:01:28,980 what the Saturn does not do is it does not go through every possible route 15 00:01:28,980 --> 00:01:34,020 from Oxford to Cambridge. There are just far too many of them for it to be 16 00:01:34,020 --> 00:01:39,270 able to do that. Instead, it turns out that there is an efficient 17 00:01:39,270 --> 00:01:45,540 algorithm for finding the shortest route between two vertices. 18 00:01:45,540 --> 00:01:51,020 And that's what I'm gonna be describing today. So the setup 19 00:01:51,020 --> 00:01:56,030 is very natural, I think. You start off with G a 20 00:01:56,030 --> 00:02:01,970 connected graph. Say this one here. And 21 00:02:01,970 --> 00:02:09,860 each edge has been assigned a positive length L of a. 22 00:02:09,860 --> 00:02:15,230 And so once you've assigned lengths to edges, it makes sense to talk about the length 23 00:02:15,230 --> 00:02:20,510 of paths. So the L length of a path P is just 24 00:02:20,510 --> 00:02:26,250 some of the lengths of it. Such as? So we use the terminology 25 00:02:26,250 --> 00:02:31,320 whole length rather than length, because we've already used, 26 00:02:31,320 --> 00:02:38,600 already defined what we mean by the length of a path. It's just the number of edges in that path. 27 00:02:38,600 --> 00:02:43,850 But we obviously want to have a notion which takes account of this function 28 00:02:43,850 --> 00:02:48,890 l assign, which assigns to each edge a positive real number. 29 00:02:48,890 --> 00:02:55,310 So that's what we talk about, the L length. But because the length is a bit of a mouthful 30 00:02:55,310 --> 00:03:02,440 in today's lecture, whenever I say length, I mean a length. 31 00:03:02,440 --> 00:03:08,030 OK, so. What we're interested in is 32 00:03:08,030 --> 00:03:13,070 how shortest paths between two vertices, X and Y. So 33 00:03:13,070 --> 00:03:18,530 an L shortest X Y path is by definition an X Y path 34 00:03:18,530 --> 00:03:23,960 that minimises the length. And it's not at all obvious 35 00:03:23,960 --> 00:03:29,240 how to find that. So, for example, in this example of these two vertices, 36 00:03:29,240 --> 00:03:34,390 X and Y. The most efficient route to get from 37 00:03:34,390 --> 00:03:39,580 one to the other is not to go along this edge here because that has length for in 38 00:03:39,580 --> 00:03:44,770 fact, the most efficient route is to take this this red path 39 00:03:44,770 --> 00:03:50,790 here, because that has length three. 40 00:03:50,790 --> 00:03:55,990 So dextrous algorithm is what we're gonna be describing today 41 00:03:55,990 --> 00:04:01,410 and what it does is it for any two vertices, X and Y, 42 00:04:01,410 --> 00:04:07,820 it finds an El shortest X Y path. 43 00:04:07,820 --> 00:04:13,630 So the idea is that we think of X as fixed in some sense 44 00:04:13,630 --> 00:04:19,370 and we're going to think about all possible vertices Y. 45 00:04:19,370 --> 00:04:24,750 Well, the algorithm does is it maintains 46 00:04:24,750 --> 00:04:30,100 a tentative distance from X. 47 00:04:30,100 --> 00:04:36,690 Called DeeVee for each Vertex V of the graph. 48 00:04:36,690 --> 00:04:42,450 So DV is going to change 49 00:04:42,450 --> 00:04:48,390 as the algorithm progresses. 50 00:04:48,390 --> 00:04:53,520 D of any Vertex V can be a non negative real number, or it can 51 00:04:53,520 --> 00:04:59,280 actually be infinity as well. 52 00:04:59,280 --> 00:05:04,280 So this function D from the vertex sets to 53 00:05:04,280 --> 00:05:09,370 the real's together with infinity. It's important to realise that this 54 00:05:09,370 --> 00:05:14,570 is going to change as the algorithm progresses. 55 00:05:14,570 --> 00:05:19,840 But at each step of the algorithm, we finalised deal view for some Vertex 56 00:05:19,840 --> 00:05:24,980 U. After that, it won't change. By the end of the 57 00:05:24,980 --> 00:05:31,070 algorithm, we've finalised of view for all of the vertices you 58 00:05:31,070 --> 00:05:36,580 and it'll be equal to the correct value, namely D of you 59 00:05:36,580 --> 00:05:41,630 will be L of P star of you, where P star view is 60 00:05:41,630 --> 00:05:46,920 some L shortest X you path. 61 00:05:46,920 --> 00:05:53,160 OK. So that's the way that the algorithm is going to work. 62 00:05:53,160 --> 00:05:58,360 So. What the algorithm does is it keeps 63 00:05:58,360 --> 00:06:04,150 track of a subset you of the vertex set. 64 00:06:04,150 --> 00:06:09,760 So initially you is the entire vertex at. So you 65 00:06:09,760 --> 00:06:14,830 is the set of vertices for which DeeVee has not yet 66 00:06:14,830 --> 00:06:19,880 been finalised. So in other words, you you should think of 67 00:06:19,880 --> 00:06:24,980 as the as the set of uncertain vertices, ones 68 00:06:24,980 --> 00:06:30,110 that we're not yet sure of for what the final deal value of that 69 00:06:30,110 --> 00:06:35,700 vertex should be. So initially, 70 00:06:35,700 --> 00:06:41,230 you is the entire vertex set. So we're not sure 71 00:06:41,230 --> 00:06:48,280 of the value of any vertex in our graph. 72 00:06:48,280 --> 00:06:53,510 Rhythm starts with D. value of the base vertex 73 00:06:53,510 --> 00:06:59,390 to be zero and. Value of every other vertex 74 00:06:59,390 --> 00:07:05,500 to be infinite. Then what does it do? 75 00:07:05,500 --> 00:07:10,680 It keeps on repeating the following step. If you 76 00:07:10,680 --> 00:07:16,350 is empty, we stop. That means that there are no vertices 77 00:07:16,350 --> 00:07:21,520 with uncertainty value. We finalised the devalue 78 00:07:21,520 --> 00:07:27,140 of all vertices. In other words, so we could stop. 79 00:07:27,140 --> 00:07:32,330 Otherwise, we pick some Vertex U in U for which 80 00:07:32,330 --> 00:07:37,490 D. U is minimal. Then what we do is we 81 00:07:37,490 --> 00:07:42,620 delete you from U. And in 82 00:07:42,620 --> 00:07:48,220 other words, we finalise. The devalue view, 83 00:07:48,220 --> 00:07:53,930 and we also do the following. For any Vertex V in U 84 00:07:53,930 --> 00:07:59,620 with V adjacent to U. And satisfying this inequality. 85 00:07:59,620 --> 00:08:04,750 Namely, that DV is strictly greater than deserve of you. Plus 86 00:08:04,750 --> 00:08:10,240 the length of the Yuva edge. If that's the case, we replace 87 00:08:10,240 --> 00:08:17,390 T V by D of you plus L. Of U. V. 88 00:08:17,390 --> 00:08:22,650 So, in other words, that has reduced the deep value of that Vertex 89 00:08:22,650 --> 00:08:27,920 V. OK. So 90 00:08:27,920 --> 00:08:32,980 it might not be obvious. What the algorithm is doing, it's really best 91 00:08:32,980 --> 00:08:39,010 to look at an example to start to get a feel for how this algorithm works. 92 00:08:39,010 --> 00:08:45,010 So here's an example. Here's our example. Here is 93 00:08:45,010 --> 00:08:50,110 our graph with the lengths assigned to its edges 94 00:08:50,110 --> 00:08:56,450 and his of text X. And, um, 95 00:08:56,450 --> 00:09:01,490 I have a label. I've met coloured all of the vertices red 96 00:09:01,490 --> 00:09:07,510 because they're in our set you of vertices for which 97 00:09:07,510 --> 00:09:13,220 the D value is not yet certain. 98 00:09:13,220 --> 00:09:18,290 So initially we set D of X to 99 00:09:18,290 --> 00:09:26,380 be zero and D of all of these other vertices to be infinite. 100 00:09:26,380 --> 00:09:31,410 OK, so the first stage is to peg the vertex 101 00:09:31,410 --> 00:09:36,690 with smallest devalue. That's X in this case, 102 00:09:36,690 --> 00:09:41,820 it is always X and we remove it from you. In other words, 103 00:09:41,820 --> 00:09:46,960 we finalises, devalue. And 104 00:09:46,960 --> 00:09:52,780 what we do is for every Vertex V adjacent to you. 105 00:09:52,780 --> 00:09:59,650 And satisfying DSV is greater than deserve you. Plus al Newfie. 106 00:09:59,650 --> 00:10:07,050 We replace TAFE by D of you. Plus l u v. 107 00:10:07,050 --> 00:10:12,420 So in other words, we should go through each of these vertices that are adjacent to 108 00:10:12,420 --> 00:10:17,830 this Vertex X. And we ask ourselves, is its current 109 00:10:17,830 --> 00:10:24,040 devalue? Greater than the deep value of X. 110 00:10:24,040 --> 00:10:30,290 Plus, the length of that edge. Joining ex to that vertex. 111 00:10:30,290 --> 00:10:35,570 Well, in this case, the answer is definitely yes, because this is infinite here and D 112 00:10:35,570 --> 00:10:40,700 of X plus one is definitely strictly less than infinity. So we should 113 00:10:40,700 --> 00:10:45,870 replace that vertex, the value of that vertex by one. 114 00:10:45,870 --> 00:10:50,930 And similarly, we should replace the T value of this vertex by three, this one by four, and this one 115 00:10:50,930 --> 00:10:56,630 by one. OK, so we've done the first step of the algorithm. 116 00:10:56,630 --> 00:11:02,960 Let's continue. Now we have to pick a 117 00:11:02,960 --> 00:11:10,000 vertex in you. In other words, one of these red vertices with minimal devalue. 118 00:11:10,000 --> 00:11:16,450 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. 119 00:11:16,450 --> 00:11:22,060 So we finalise its devalue. That means we remove it from the set you. 120 00:11:22,060 --> 00:11:27,070 So it's not that vertex is no longer red. And then we look at 121 00:11:27,070 --> 00:11:32,080 all of its neighbours that are in you in this case, 122 00:11:32,080 --> 00:11:38,080 there's just the one of them. This vertex here and we ask ourselves, 123 00:11:38,080 --> 00:11:43,300 is the devalue of that Vertex V strictly greater than the D value 124 00:11:43,300 --> 00:11:49,270 of you? Plus the length of the edge u. V. Yes, it is, 125 00:11:49,270 --> 00:11:54,820 because three is greater than one plus one. So we should replace this three 126 00:11:54,820 --> 00:12:00,270 by a two. Now we continue. 127 00:12:00,270 --> 00:12:05,640 So the again, we look at the vertex with smallest devalue 128 00:12:05,640 --> 00:12:10,980 is this one on the top. So we finalise that and then we look at all of its neighbours 129 00:12:10,980 --> 00:12:16,270 and we ask ourselves, is the deep value of this case? 130 00:12:16,270 --> 00:12:23,400 All of its neighbours knew this. This is just one of them. Is that devalue 131 00:12:23,400 --> 00:12:29,880 strictly greater than the value of you? Plus the length of that edge? 132 00:12:29,880 --> 00:12:35,040 Well, in this case, four is less than one plus five. So we don't change 133 00:12:35,040 --> 00:12:40,090 that. OK, so now 134 00:12:40,090 --> 00:12:46,540 we look at the next one here, this is the next vertex that we 135 00:12:46,540 --> 00:12:53,250 this is the next vertex and you with smaller Steve. We finalised that one. 136 00:12:53,250 --> 00:12:58,710 We look at all of its neighbours in you, that's just this one. And 137 00:12:58,710 --> 00:13:03,840 we say, should we be decreasing their devalue? Well, in this case, 138 00:13:03,840 --> 00:13:09,330 we should, because four is greater than two plus one. So we should 139 00:13:09,330 --> 00:13:16,570 reduce that to three. Now it comes the final step of the algorithm. 140 00:13:16,570 --> 00:13:24,310 This is the last vertex, and we finalise its value and we stop. 141 00:13:24,310 --> 00:13:29,450 And as you can see, the values on these vertices really 142 00:13:29,450 --> 00:13:36,500 are correct. They do represent the length of the shortest path. 143 00:13:36,500 --> 00:13:41,740 The L length of the shortest path from X to that vertex. 144 00:13:41,740 --> 00:13:47,320 So, for example, we saw that the shortest path from X to this vertex here 145 00:13:47,320 --> 00:13:52,330 was going around the edges with length one. 146 00:13:52,330 --> 00:13:57,370 And so that the that the correct devalue there 147 00:13:57,370 --> 00:14:02,790 is indeed three. OK. So it's done 148 00:14:02,790 --> 00:14:08,280 the correct job. In fact, 149 00:14:08,280 --> 00:14:16,190 the extras algorithm can be used to do more. 150 00:14:16,190 --> 00:14:21,260 What it can do is it can be used for 151 00:14:21,260 --> 00:14:26,450 any vertex acts to construct a spanning treaty 152 00:14:26,450 --> 00:14:31,690 with the following property. If any vertex Y 153 00:14:31,690 --> 00:14:37,120 in the graph. The unique x y path 154 00:14:37,120 --> 00:14:42,160 in T is actually the shortest and L 155 00:14:42,160 --> 00:14:47,320 shortest x y path, so it's quite 156 00:14:47,320 --> 00:14:52,940 surprising in my view, that such a tree should exist. 157 00:14:52,940 --> 00:14:58,510 We call such a treaty an El shortest paths tree rooted 158 00:14:58,510 --> 00:15:03,650 at X. So let me give you an example. I've highlighted here 159 00:15:03,650 --> 00:15:10,760 in red. Such a shortest paths tree. 160 00:15:10,760 --> 00:15:16,640 And you can easily cheque that the shortest way of guessing from any vertex 161 00:15:16,640 --> 00:15:24,280 to X is to go via the edges in this tree. 162 00:15:24,280 --> 00:15:29,410 So that is what the shortest paths tree that that's is defining property, that the shortest 163 00:15:29,410 --> 00:15:34,630 way of getting from any vertex to acts is to follow the unique path in 164 00:15:34,630 --> 00:15:41,530 the tree from that vertex to X. 165 00:15:41,530 --> 00:15:46,570 OK. So how come we had what it takes just algorithm to how does it 166 00:15:46,570 --> 00:15:52,090 create this tree? So we're going to describe 167 00:15:52,090 --> 00:15:57,220 how to obtain the tree tea. OK, 168 00:15:57,220 --> 00:16:02,520 so here's our example that we're looking at. So what it does 169 00:16:02,520 --> 00:16:08,180 is for each vertex v. other than the base Vertex X. 170 00:16:08,180 --> 00:16:13,370 We define its parent. So the parent of 171 00:16:13,370 --> 00:16:18,520 a Vertex V. Is the last vertex 172 00:16:18,520 --> 00:16:24,090 you. With a property that we replaced, a V 173 00:16:24,090 --> 00:16:31,190 by D of U plus L u v during the algorithm. 174 00:16:31,190 --> 00:16:36,190 So if you remember, for every vertex. We kept this tentative 175 00:16:36,190 --> 00:16:41,280 notion of distance D from X. 176 00:16:41,280 --> 00:16:48,830 And this deal, as the algorithm progressed, kept on going down. 177 00:16:48,830 --> 00:16:54,840 And at some point, it stops. Now, 178 00:16:54,840 --> 00:17:00,210 when it goes down. What? The way that it goes down is that 179 00:17:00,210 --> 00:17:05,490 Davey is goes down. So the value of you plus l 180 00:17:05,490 --> 00:17:10,530 u v for some vertex you. And 181 00:17:10,530 --> 00:17:15,720 so when it goes down for the last time that you is called the parent 182 00:17:15,720 --> 00:17:20,720 of the. So, for example, in this case here, when we ran the 183 00:17:20,720 --> 00:17:26,420 algorithm, we we first of all finalised X 184 00:17:26,420 --> 00:17:31,850 and then we finalised V, this Vertex V here. And 185 00:17:31,850 --> 00:17:36,860 before we finalised it, we reduced the D value of V by 186 00:17:36,860 --> 00:17:41,870 saying that it was the D value of X plus the length of this edge. So in 187 00:17:41,870 --> 00:17:47,390 other words, X is the parent of V K, so I've drawn in in read 188 00:17:47,390 --> 00:17:52,430 the parent to V. The next stage 189 00:17:52,430 --> 00:17:58,070 of the algorithm was to finalise this vertex here 190 00:17:58,070 --> 00:18:03,170 that had its value, had gone down from infinity to one. And when it went down 191 00:18:03,170 --> 00:18:08,210 from infinity to one, that was because it was equal to the deep value of 192 00:18:08,210 --> 00:18:13,220 X plus the length of that edge. So the parents of this vertex here 193 00:18:13,220 --> 00:18:18,440 is also X. The parents of this vertex here is this 194 00:18:18,440 --> 00:18:23,960 vertex B and so on. And so what we do is we create 195 00:18:23,960 --> 00:18:29,100 our tree. So we obtain our treaty. By 196 00:18:29,100 --> 00:18:34,130 drawing an edge from each Vertex V. Other 197 00:18:34,130 --> 00:18:40,260 than X. To its parent. 198 00:18:40,260 --> 00:18:45,420 OK, so this is the algorithm, and it's not at all 199 00:18:45,420 --> 00:18:50,700 clear that it does the right job. And in fact, I'm gonna be spending 200 00:18:50,700 --> 00:18:55,840 the rest of the lecture explaining why the algorithm does 201 00:18:55,840 --> 00:19:00,880 book. So I 202 00:19:00,880 --> 00:19:06,250 want to start by proving Alema, which she's going to give us some 203 00:19:06,250 --> 00:19:11,750 structural results about. Te. And about 204 00:19:11,750 --> 00:19:17,330 de. So it has two parts to it. The first 205 00:19:17,330 --> 00:19:23,580 part of the Lemmer is that T is indeed a tree. 206 00:19:23,580 --> 00:19:29,020 It's clearly, therefore, spanning tree. Because if you remember, the way it was defined was 207 00:19:29,020 --> 00:19:34,050 for every vertex other than X, there was an edge going 208 00:19:34,050 --> 00:19:39,210 from that vertex to its parent. So in other words, 209 00:19:39,210 --> 00:19:44,470 this really does cover every single vertex of the graph. 210 00:19:44,470 --> 00:19:52,440 So once we've proved this, Lemmer proves that it's a tree will have the tea is a spanning tree. 211 00:19:52,440 --> 00:19:57,670 But we won't yet prove that it's the shortest paths spanning tree. 212 00:19:57,670 --> 00:20:02,850 Instead, what we'll do is prove the following. 213 00:20:02,850 --> 00:20:07,980 For each. Vertex, you. Do 214 00:20:07,980 --> 00:20:13,380 you view will show is equal to the length of pay, 215 00:20:13,380 --> 00:20:21,920 if you pay, if you is the unique X, you pass in T. 216 00:20:21,920 --> 00:20:28,250 So that'll be clearly a useful thing to do. So the final thing that we claim 217 00:20:28,250 --> 00:20:33,740 is that the shortest way of getting from you to X 218 00:20:33,740 --> 00:20:38,780 is by following this path. This unique path p 219 00:20:38,780 --> 00:20:44,080 u. So we haven't proved that. And this lemma isn't claiming that yet. But 220 00:20:44,080 --> 00:20:49,130 what is claiming is the D of U is the length of that path. 221 00:20:49,130 --> 00:20:54,380 P u in T. OK, 222 00:20:54,380 --> 00:21:00,080 so let's prove this lemme. 223 00:21:00,080 --> 00:21:05,160 So at each step. We have a subset. 224 00:21:05,160 --> 00:21:10,260 You and can, let's see, be 225 00:21:10,260 --> 00:21:15,570 the complement of you, so see is the set 226 00:21:15,570 --> 00:21:20,650 of vertices for which the D value is certain. That's what's 227 00:21:20,650 --> 00:21:26,760 called C. It's been finalised. Those are the vertices which is finalised. 228 00:21:26,760 --> 00:21:31,850 And suddenly the case for every finalised vertex with finalised 229 00:21:31,850 --> 00:21:37,090 devalue. We know what its parent is. Because 230 00:21:37,090 --> 00:21:42,220 we know the last time that we decrease that devalue, and hence we know 231 00:21:42,220 --> 00:21:47,410 what the parent of that vertex is, so we can certainly have defined 232 00:21:47,410 --> 00:21:53,160 the parents of all the vertices in see. 233 00:21:53,160 --> 00:21:58,470 OK, so let me just run through this algorithm again, in this particular case, 234 00:21:58,470 --> 00:22:03,720 keeping track of the red vertices, which are the ones 235 00:22:03,720 --> 00:22:08,720 for which we're not yet certain. So as we run 236 00:22:08,720 --> 00:22:13,880 through the algorithm, you can see that the black vertices, 237 00:22:13,880 --> 00:22:19,250 one complement of you, is growing. 238 00:22:19,250 --> 00:22:24,340 So that's those are the vertices and see. 239 00:22:24,340 --> 00:22:30,010 So let TFC be obtained by drawing an edge 240 00:22:30,010 --> 00:22:36,000 from each vertex. In C minus six to its parent. 241 00:22:36,000 --> 00:22:41,040 So V, T.C., his C. So here's an example. For example, 242 00:22:41,040 --> 00:22:46,740 we're halfway through the algorithm here. What we've done is 243 00:22:46,740 --> 00:22:52,650 we've finalised the deep value of X and we finalised 244 00:22:52,650 --> 00:22:58,050 the value of this vertex here. So see consists 245 00:22:58,050 --> 00:23:05,640 of these two vertices and you is the remaining vertices. 246 00:23:05,640 --> 00:23:11,580 And more so because we finalised the value of this bottom vertex, 247 00:23:11,580 --> 00:23:17,490 we know what its parent is. We know that it's X. And 248 00:23:17,490 --> 00:23:23,020 so we defined T.C., which is the 249 00:23:23,020 --> 00:23:28,290 fact that the graph, which is obtained by going through every single vertex 250 00:23:28,290 --> 00:23:33,540 in sea other than the base vertex. And adding 251 00:23:33,540 --> 00:23:39,810 in the edge, which goes from that vertex to its parent. 252 00:23:39,810 --> 00:23:44,880 So V of T, c, c. 253 00:23:44,880 --> 00:23:50,030 The next stage, for example, we've enlarged see 254 00:23:50,030 --> 00:23:56,190 and that, by and large, TFC. 255 00:23:56,190 --> 00:24:02,370 And so on and so forth. So you can see that what we're doing 256 00:24:02,370 --> 00:24:07,410 is we're gradually building tea. We're just adding in the edges of 257 00:24:07,410 --> 00:24:12,600 tea. One by one. And at any given stage, 258 00:24:12,600 --> 00:24:17,620 we've got this craft, T.S. So what we can do is we're going to 259 00:24:17,620 --> 00:24:22,900 show by induction on the number of cardinality of C, 260 00:24:22,900 --> 00:24:28,340 the T C is a tree. And for each vertex 261 00:24:28,340 --> 00:24:33,490 you have TSC. In other words, each you in, see? We have that 262 00:24:33,490 --> 00:24:39,410 day of U is L of pay off here. 263 00:24:39,410 --> 00:24:44,680 In other words, the length of the unique X you pass in 264 00:24:44,680 --> 00:24:49,800 T.S. So that will clearly do the job. So the 265 00:24:49,800 --> 00:24:54,930 way this is working is we're building up a T. One 266 00:24:54,930 --> 00:25:00,300 edge at a time. And as we're going along, we're proving 267 00:25:00,300 --> 00:25:05,430 what we need to for just the 268 00:25:05,430 --> 00:25:10,540 vertices in C. So by the time 269 00:25:10,540 --> 00:25:15,540 that the process is finished and C is everything 270 00:25:15,540 --> 00:25:21,040 will have proved Alema. OK, 271 00:25:21,040 --> 00:25:26,920 so that's just a restatement of what I wrote down before, we're going to show by induction 272 00:25:26,920 --> 00:25:33,180 on the cardinality of C. The tacy is a tree. 273 00:25:33,180 --> 00:25:39,650 And for each vertex, you, A.C. and otherwise, each you in see, 274 00:25:39,650 --> 00:25:44,820 we have the D of you is L of P u. 275 00:25:44,820 --> 00:25:50,810 OK, so the base case is pretty straightforward. 276 00:25:50,810 --> 00:25:56,430 The very start in cases where the vertex set of TCE is X. 277 00:25:56,430 --> 00:26:02,440 As just a single vertex Senate, no edges. It's definitely a tree. And 278 00:26:02,440 --> 00:26:07,470 D, if that Vertex X is the correct value, it's zero, which is L of P 279 00:26:07,470 --> 00:26:12,510 X. OK, so now we're going to the 280 00:26:12,510 --> 00:26:17,680 induction step. So I suppose we've got to this stage 281 00:26:17,680 --> 00:26:22,750 here. We're now going to add in one more 282 00:26:22,750 --> 00:26:31,550 element to see. We're going to finalise one more, the devalue of one more vertex. 283 00:26:31,550 --> 00:26:37,010 So the next one, next vertex we're going to finalise is this vertex 284 00:26:37,010 --> 00:26:43,110 you it's the one for which T is minimal in you. 285 00:26:43,110 --> 00:26:48,940 When we do that, we delete you from our set. 286 00:26:48,940 --> 00:26:54,000 But you have to seise that for which the devalue is uncertain and thereby we 287 00:26:54,000 --> 00:26:59,260 add it to see. And we add 288 00:26:59,260 --> 00:27:04,600 an edge you, which joins you to its parent, 289 00:27:04,600 --> 00:27:10,110 which lies inside, see? So in other words, we add 290 00:27:10,110 --> 00:27:15,870 we know by induction that the inductive hypothesis is that 291 00:27:15,870 --> 00:27:22,500 what we've created in green so far, T.C., is a tree. 292 00:27:22,500 --> 00:27:29,590 And what we're doing is we're adding a leaf to that tree. And so it stays a tree. 293 00:27:29,590 --> 00:27:34,690 OK, so that's one part of the thing that we have to show that each 294 00:27:34,690 --> 00:27:41,580 time we add an edged T.C. staes tree. 295 00:27:41,580 --> 00:27:47,690 We also need to cheque that when we add in this vertex, you. 296 00:27:47,690 --> 00:27:53,260 Day of U is L of pay if you. 297 00:27:53,260 --> 00:27:59,560 OK, so what is D of you? Well, D of you remember, 298 00:27:59,560 --> 00:28:04,720 he's been going down on the very last time, went down. We set it equal 299 00:28:04,720 --> 00:28:09,990 to DSV plus L v you. For some Vertex 300 00:28:09,990 --> 00:28:15,120 V, which by definition is the parent. 301 00:28:15,120 --> 00:28:20,670 So Day of U is equal to D.V. plus L. V you for V 302 00:28:20,670 --> 00:28:25,920 the parent view. The lies inside 303 00:28:25,920 --> 00:28:30,930 see, and so by the inductive hypothesis, DV is 304 00:28:30,930 --> 00:28:36,000 equal to the length of the path, unique path 305 00:28:36,000 --> 00:28:41,680 in the tree. Joining V to X i.e. A 306 00:28:41,680 --> 00:28:48,630 so deep V is how Peevey. 307 00:28:48,630 --> 00:28:53,700 But out of PVA plus, our view is the length of pay you 308 00:28:53,700 --> 00:29:00,160 because the unique path in the tree joining you to X. 309 00:29:00,160 --> 00:29:05,460 We use it a leaf of the tree, so it travels along 310 00:29:05,460 --> 00:29:11,270 U. V. And then it does. Peevey did. 311 00:29:11,270 --> 00:29:17,410 And so I've shown what I needed to show, namely that for this new vertex 312 00:29:17,410 --> 00:29:22,440 deal of you is equal to L. P. 313 00:29:22,440 --> 00:29:29,350 And so I'm done by induction. 314 00:29:29,350 --> 00:29:35,720 OK, so what have we got to. Well. 315 00:29:35,720 --> 00:29:43,390 We've been building this tree tea and we now know that tea is a tree. 316 00:29:43,390 --> 00:29:48,390 And we also know that for every vertex. It's 317 00:29:48,390 --> 00:29:53,700 devalue is equal to the length in the tree. 318 00:29:53,700 --> 00:29:58,880 From that vertex to X. But what we need to show 319 00:29:58,880 --> 00:30:06,020 is that actually the devalue is equal to the. 320 00:30:06,020 --> 00:30:12,700 The shortest possible route in the whole graph from that vertex tax. 321 00:30:12,700 --> 00:30:17,710 In other words, we've got to show that there is no 322 00:30:17,710 --> 00:30:22,750 quicker way of getting from that vertex to X other than going by the tree. 323 00:30:22,750 --> 00:30:27,940 T. So in other words, what we've got to show, and this will complete the proof 324 00:30:27,940 --> 00:30:33,070 that the algorithm works. We're going to show that T is 325 00:30:33,070 --> 00:30:40,960 an L shortest paths tree rooted ATEX. 326 00:30:40,960 --> 00:30:46,020 OK, so we've defined D of you. I'm going to define 327 00:30:46,020 --> 00:30:51,130 D star of you as follows. So if each vertex you in 328 00:30:51,130 --> 00:30:56,470 Beijing D star of you is L of peace, 329 00:30:56,470 --> 00:31:01,690 star of you for some L shortest x you path p 330 00:31:01,690 --> 00:31:06,760 star you. OK, so it makes 331 00:31:06,760 --> 00:31:12,040 sense to consider this quantity we call our quantity D. If you. 332 00:31:12,040 --> 00:31:17,520 And we want to prove that it's equal to 333 00:31:17,520 --> 00:31:22,880 the length of the shortest path from you to X. So we've defined 334 00:31:22,880 --> 00:31:28,520 this DENR of you to be the actual length of the shortest path from 335 00:31:28,520 --> 00:31:33,550 you to Axe. So we want to show that day of you. His teacher, 336 00:31:33,550 --> 00:31:39,860 Dorothy. So we're going to show by induction that each step of the algorithm 337 00:31:39,860 --> 00:31:45,320 when you. Is deleted. We have D of you is equal to D Starkie. 338 00:31:45,320 --> 00:31:51,060 And so we'll be done. 339 00:31:51,060 --> 00:31:56,400 OK, so the base case is. So we're we're inducting, obviously, 340 00:31:56,400 --> 00:32:01,560 on the cardinality of C. 341 00:32:01,560 --> 00:32:07,650 So the base case is when we have just a single vertex, 342 00:32:07,650 --> 00:32:12,670 namely when you is X, well, D of you. Is that 343 00:32:12,670 --> 00:32:17,760 the final value of D of you? I mean, delete it from from U u 344 00:32:17,760 --> 00:32:23,050 equals X zero. And that's the correct value, 345 00:32:23,050 --> 00:32:28,880 namely the the length of the shortest path from X. X has zero. 346 00:32:28,880 --> 00:32:34,050 OK, so that's the base case. What about the inductive 347 00:32:34,050 --> 00:32:39,740 step? OK, so. 348 00:32:39,740 --> 00:32:44,990 What we're trying to show is the day of you is DENR of you, 349 00:32:44,990 --> 00:32:50,450 every vertex, you join that one vertex. This time we do it considering the vertex 350 00:32:50,450 --> 00:32:55,850 where we delete you from our set here. In other words, when we finalise the value 351 00:32:55,850 --> 00:33:02,020 of D. Well, clearly, de. 352 00:33:02,020 --> 00:33:09,100 Star of you is less than or equal to D of you. 353 00:33:09,100 --> 00:33:14,100 Why is that D star if you. Is the length of the shortest path from you to 354 00:33:14,100 --> 00:33:19,340 X? And we've shown that dear view is the length of the shortest 355 00:33:19,340 --> 00:33:24,460 path from you to X in the tree. So therefore, 356 00:33:24,460 --> 00:33:30,000 Daystar you is definitely less than or equal to D.F. you. 357 00:33:30,000 --> 00:33:35,520 So the only way they could fail to be equal is if the inequality was strict. So I suppose 358 00:33:35,520 --> 00:33:40,880 for contradiction, the day of you is strictly greater than de star. 359 00:33:40,880 --> 00:33:45,950 If you. OK. 360 00:33:45,950 --> 00:33:52,980 As usual. Let's see. Viji minus you. These are the vertices that we have finalised. 361 00:33:52,980 --> 00:33:58,010 And we know that. So we're proving that as we 362 00:33:58,010 --> 00:34:04,300 finalise each vertex. D If that vertex is t star of that vertex. 363 00:34:04,300 --> 00:34:09,310 So for the vertices that we finalised, know every Vertex V in 364 00:34:09,310 --> 00:34:16,750 our treaty C. We know that D star of his TV. 365 00:34:16,750 --> 00:34:21,950 OK. So the setup is something a bit like this. This is some 366 00:34:21,950 --> 00:34:27,040 graph. This is my base, Vertex X. 367 00:34:27,040 --> 00:34:32,350 And so you so so did these these vertices in green that the vertices 368 00:34:32,350 --> 00:34:39,700 and see, they are the ones whose deep value has been finalised. 369 00:34:39,700 --> 00:34:45,660 And also in green is the tree, T.C. 370 00:34:45,660 --> 00:34:51,560 And what we're doing now is we've finalised some new vertex you. 371 00:34:51,560 --> 00:34:56,570 So you is the vertex who's devalue, we're now just finalising. So this is the 372 00:34:56,570 --> 00:35:01,920 stage we're at in the algorithm. And what we want to do 373 00:35:01,920 --> 00:35:07,340 is we want to show the deeds of you is equal to these star. 374 00:35:07,340 --> 00:35:12,500 And we're assuming for a contradiction that do you view is strictly greater 375 00:35:12,500 --> 00:35:18,480 than dystrophy. OK. So 376 00:35:18,480 --> 00:35:23,760 we have peace star of you. This is the length of the shortest path. 377 00:35:23,760 --> 00:35:29,300 In the graph from X to U. 378 00:35:29,300 --> 00:35:34,920 So it clearly starts at X. 379 00:35:34,920 --> 00:35:40,030 Which is in SI. And it ends in 380 00:35:40,030 --> 00:35:45,570 our set you. And so there is some first point 381 00:35:45,570 --> 00:35:50,780 when it leaves. See? So let y y primed 382 00:35:50,780 --> 00:35:56,820 be the first edge of this shortest path p style you. 383 00:35:56,820 --> 00:36:02,080 With why not in you? In other words, why in C? But why primed 384 00:36:02,080 --> 00:36:07,420 in, you know, this is our first time, this pasto, you leaves 385 00:36:07,420 --> 00:36:12,530 the tree. It could actually happen that it's the 386 00:36:12,530 --> 00:36:18,930 that it ends at you. That's completely fine, but it might not. 387 00:36:18,930 --> 00:36:26,860 OK, so we're going to focus on this edge y y primed. 388 00:36:26,860 --> 00:36:33,220 Now, by induction, we know that that 389 00:36:33,220 --> 00:36:38,680 all of the vertices in this tree, T.S. 390 00:36:38,680 --> 00:36:43,870 They have the correct devalue, namely D of Y is equal 391 00:36:43,870 --> 00:36:51,630 to D star of Y particular for this vertex y. 392 00:36:51,630 --> 00:36:56,700 OK, so now we have a sequence of inequalities. Some of them are more obvious than 393 00:36:56,700 --> 00:37:02,010 others. The first one is possibly the least 394 00:37:02,010 --> 00:37:07,040 obvious. I claim that day of why primed is 395 00:37:07,040 --> 00:37:15,730 less than or equal to D of y plus l. Y. Y primed. 396 00:37:15,730 --> 00:37:23,890 OK, so the first inequality is because of the the update rule. 397 00:37:23,890 --> 00:37:29,260 So. What it does is. 398 00:37:29,260 --> 00:37:35,930 Each time we put a vertex into C, we finalise it. 399 00:37:35,930 --> 00:37:42,990 What we do is we look at all of its neighbours in you. And we say. 400 00:37:42,990 --> 00:37:48,810 Is there D value greater than D of this vertex Y 401 00:37:48,810 --> 00:37:54,910 plus the length of the edge? So when we finalised 402 00:37:54,910 --> 00:38:00,000 the deal value of Y. We would have done this for 403 00:38:00,000 --> 00:38:06,920 this edge here, so we would have looked at the deep value for why primed and we would have said. 404 00:38:06,920 --> 00:38:12,320 Is it strictly greater than the value of Y plus l. 405 00:38:12,320 --> 00:38:18,330 Y y. Primed. And if it was, we would have 406 00:38:18,330 --> 00:38:23,720 decreased the T value of Y prime down to that value. 407 00:38:23,720 --> 00:38:30,780 Well, maybe at later steps in the algorithm, the devalue of why Prime went down even further. 408 00:38:30,780 --> 00:38:35,900 But that's fine. We get the inequality that day of why primed is less than or equal to 409 00:38:35,900 --> 00:38:41,770 deserve. Why? Plus l y y primed. 410 00:38:41,770 --> 00:38:47,060 OK. Next pit is fairly obvious. We've already shown that 411 00:38:47,060 --> 00:38:52,340 because of the induction hypothesis, D of Y is equal to D staff Y. So 412 00:38:52,340 --> 00:38:59,690 these two are equal. And by definition. 413 00:38:59,690 --> 00:39:04,820 D staff. Why is L of P star, why the shortest possible 414 00:39:04,820 --> 00:39:09,960 path from Y to X? 415 00:39:09,960 --> 00:39:15,030 And I claim that L. Of Peace star Y plus l y y 416 00:39:15,030 --> 00:39:20,310 primed is less than or equal to Hall of Peace star you. 417 00:39:20,310 --> 00:39:25,960 So why is that? OK, so peace star, you 418 00:39:25,960 --> 00:39:31,020 is a shortest path between X 419 00:39:31,020 --> 00:39:36,050 and you. So that means that any sub path of 420 00:39:36,050 --> 00:39:41,420 it also has to be a shortest path. Joining two 421 00:39:41,420 --> 00:39:46,730 versus the two ends of that path. Otherwise, there would be a way 422 00:39:46,730 --> 00:39:52,220 of shortening peacetime. You. 423 00:39:52,220 --> 00:39:57,760 So that means that the. Shortest 424 00:39:57,760 --> 00:40:03,150 way of getting from Y to X. It's to go fire 425 00:40:03,150 --> 00:40:08,290 peacetime you. So 426 00:40:08,290 --> 00:40:13,510 that means that L. Of P star, why 427 00:40:13,510 --> 00:40:18,550 shortest way? Plus, the length of why 428 00:40:18,550 --> 00:40:23,700 why primed? Well, that's the total length 429 00:40:23,700 --> 00:40:29,030 of this sub path from X to Y primed. 430 00:40:29,030 --> 00:40:35,160 That's a subset of the entire of peace star you. And so we get the inequality. 431 00:40:35,160 --> 00:40:40,160 Hell of peace star y plus l y y y pride is less 432 00:40:40,160 --> 00:40:45,460 trinkle to l p start you. 433 00:40:45,460 --> 00:40:51,210 OK. So al of peace star you is by definition 434 00:40:51,210 --> 00:40:56,240 and de star, if you that's what how these stars defined it's. 435 00:40:56,240 --> 00:41:01,380 It's the shortest possible length, the shortest possible path from you to 436 00:41:01,380 --> 00:41:07,920 X. And we're assuming that piece W is such path. 437 00:41:07,920 --> 00:41:13,260 And remember, we were supposing for a contradiction 438 00:41:13,260 --> 00:41:19,880 that Daystar Star, you was strictly less than de if you. 439 00:41:19,880 --> 00:41:25,010 So putting all these together, we get that the deep value 440 00:41:25,010 --> 00:41:30,480 of Y primed. He's strictly less than the devalue. 441 00:41:30,480 --> 00:41:35,580 You. 442 00:41:35,580 --> 00:41:42,070 And that is a contradiction. So why? 443 00:41:42,070 --> 00:41:47,890 If you remember, the way the algorithm works is 444 00:41:47,890 --> 00:41:53,130 it chooses to finalise the default. You. Of a vertex 445 00:41:53,130 --> 00:41:58,720 in our set you with smallest possible D. 446 00:41:58,720 --> 00:42:04,480 And we're supposing that it's finalising this vertex you. 447 00:42:04,480 --> 00:42:09,940 But it shouldn't have done because the devalue of Y primed is strictly 448 00:42:09,940 --> 00:42:15,340 less than it. That's what we just proved. And so, in other words, it should 449 00:42:15,340 --> 00:42:20,470 have. Instead of finalising the value of you, it should have finalised 450 00:42:20,470 --> 00:42:26,050 the T value of Y primed. Or some other vertex with even smaller T value. 451 00:42:26,050 --> 00:42:33,440 That is a new. So that's a contradiction that contradicts her choice of U. 452 00:42:33,440 --> 00:42:38,450 And so what is what what what what hypothesis 453 00:42:38,450 --> 00:42:43,940 is that contradicts then? So that contradicts the hypothesis that that 454 00:42:43,940 --> 00:42:48,950 Daystar view was strictly less than did you. 455 00:42:48,950 --> 00:42:53,960 So we did use the D of view is actually equal to D. Starr, if you. And that is what we 456 00:42:53,960 --> 00:42:59,190 needed to prove. So that completes 457 00:42:59,190 --> 00:43:04,380 the proof of the theorem that T is an 458 00:43:04,380 --> 00:43:10,670 L shortest path, tree rooted attacks. 459 00:43:10,670 --> 00:43:16,190 And therefore, that completes the proof that dextrous algorithm 460 00:43:16,190 --> 00:43:21,680 works. Something is quite a remarkable algorithm 461 00:43:21,680 --> 00:43:26,990 because it's extremely efficient. Let's just analyse its running 462 00:43:26,990 --> 00:43:32,110 time. So the running time of this algorithm is 463 00:43:32,110 --> 00:43:37,120 is big. Oh. Of the number of vertices of the graph times, the number 464 00:43:37,120 --> 00:43:45,080 of edges in the graph. So let's just understand why that is. 465 00:43:45,080 --> 00:43:50,420 Well, at each stage, what we're doing is we are 466 00:43:50,420 --> 00:43:56,880 finalising the deep value of a lot 467 00:43:56,880 --> 00:44:02,690 of other vertex. So we're running through each of the vertices 468 00:44:02,690 --> 00:44:08,240 one by one. So the number of steps 469 00:44:08,240 --> 00:44:13,440 his we do that is his of the the 470 00:44:13,440 --> 00:44:19,500 number of vertices. But what do we do at each stage? 471 00:44:19,500 --> 00:44:24,610 Well, for that given vertex, we look at 472 00:44:24,610 --> 00:44:30,760 all of its neighbours and we 473 00:44:30,760 --> 00:44:35,860 possibly reduce their T values. Well, how many neighbours does that 474 00:44:35,860 --> 00:44:42,090 vertex have? Well, certainly at most the number of edges in the graph. 475 00:44:42,090 --> 00:44:47,190 So. The number of devalues that it needs to change at any 476 00:44:47,190 --> 00:44:52,830 given stage is the most the the the number of edges in the graph. And so 477 00:44:52,830 --> 00:44:58,080 the total running time is equal to most the number of vertices times, 478 00:44:58,080 --> 00:45:03,690 the number of hedges. In fact, Ashley, 479 00:45:03,690 --> 00:45:08,700 you can slightly rearrange takes his album somewhat using slightly 480 00:45:08,700 --> 00:45:14,250 better implementation, which we emit, which gives her a better running time, which is where 481 00:45:14,250 --> 00:45:19,470 the number we were at, which is Bego, of the number of edges, plus the number 482 00:45:19,470 --> 00:45:24,500 of vertices times log of the number of vertices. But in any 483 00:45:24,500 --> 00:45:30,110 case, the version of the algorithm that I described here really is 484 00:45:30,110 --> 00:45:35,330 very efficient. It's bounded above by 485 00:45:35,330 --> 00:45:40,340 a polynomial in the number of vertices and the number of edges. And that is 486 00:45:40,340 --> 00:45:45,770 what we're taking is a working definition of efficient. In particular, 487 00:45:45,770 --> 00:45:50,780 it's much, much more efficient than the naive algorithm of 488 00:45:50,780 --> 00:45:56,730 just looking at all possible paths between a pair of vertices. 489 00:45:56,730 --> 00:46:01,860 Looking at the length of each and just taking the minimum that that takes far, 490 00:46:01,860 --> 00:46:27,520 far too. OK, so that completes this lecture.