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.