1
00:00:03,960 --> 00:00:08,544
To put our, all our algorithms into
context and better understand them. What

2
00:00:08,544 --> 00:00:13,907
we'll do now is go through some basic
properties. Of shortest paths in, edge

3
00:00:13,907 --> 00:00:20,650
weighted directed graphs. So, what kind of
data structures are gonna need, first of

4
00:00:20,650 --> 00:00:27,152
all? Our goal is to find the shortest path
from s to every other vertex. so, the

5
00:00:27,152 --> 00:00:32,946
first observation is that there's gonna be
a shortest paths tree solution. well if no

6
00:00:32,946 --> 00:00:37,669
two paths have the same length, then
certainly, it's gonna be, such a solution

7
00:00:37,669 --> 00:00:42,930
and there's a number of ways to convince
yourself, that there's gonna be a tree. if

8
00:00:42,930 --> 00:00:47,832
you've got two paths to the same vertex,
you can delete the last edge in one of

9
00:00:47,832 --> 00:00:52,755
them and keep going until all that's left
is a tree, for example. So what we wanna

10
00:00:52,755 --> 00:01:00,219
do is compute a tree. now, we've done
that, in several algorithms before. And a

11
00:01:00,219 --> 00:01:07,573
reasonable way to represent the shortest
path's tree is to use two vertex indexed

12
00:01:07,573 --> 00:01:14,578
arrays. the first one is for every vertex.
Compute the length of the shortest path

13
00:01:14,578 --> 00:01:20,683
from s to that vertex. So in this case, we
have this shortest pastry, and we'll keep

14
00:01:20,683 --> 00:01:27,313
the length from the shortest path from the
source, zero to each vertex. So zero two,

15
00:01:27,321 --> 00:01:33,812
two, the length of that shortest path is
26. 027 two, seven, it's 0.60 and like

16
00:01:33,812 --> 00:01:41,063
that. And so, because you go from zero to
2.36 and from two to 7.34 you get 60., and

17
00:01:41,063 --> 00:01:47,133
so forth. And the other thing is, we've
done before is use parent link

18
00:01:47,133 --> 00:01:54,193
representation, where edge 2V is gonna be
the last edge that takes us to V. And by

19
00:01:54,193 --> 00:01:59,856
following back through that array, we can
get the path, as we have done several

20
00:01:59,856 --> 00:02:05,340
times before. If we want the path from
zero to six, we go to edge 26 and says

21
00:02:05,340 --> 00:02:10,841
well, the last thing we do is three to six
then we go to three and say the way we got

22
00:02:10,841 --> 00:02:16,342
to three is from seven We go to seven say
the way we got to seven is from two We go

23
00:02:16,342 --> 00:02:21,647
to two and say that's the way we got to
zero And if we put all those things on a

24
00:02:21,647 --> 00:02:26,820
stack, then we can return them as an
noterable to the client and that gives the

25
00:02:26,820 --> 00:02:32,125
edges on the shortest path. So that's the
data structures that we're going to use

26
00:02:32,125 --> 00:02:38,804
for shortest paths. this is, actually the
code that does, what I just said. The

27
00:02:38,804 --> 00:02:45,309
client query give me the distance, it
just, returns, uses v to index into the

28
00:02:45,556 --> 00:02:52,472
instance array and returns the distance.
and if the client asks for the path, then

29
00:02:52,472 --> 00:03:00,839
we make a stack and then, its variable e
is a directed edge, and we started edge

30
00:03:00,839 --> 00:03:07,353
2v. And as long as it's not null, we push
it onto the path and then go to the edge

31
00:03:07,353 --> 00:03:13,665
two entry for the vertex that we came from
and that gives the vertex that we came

32
00:03:13,665 --> 00:03:20,207
from to get to that vertex and keep going
until we run out of vertices which happens

33
00:03:20,207 --> 00:03:26,365
at the source. Then return to path and
that's iterable that gives the client the

34
00:03:26,365 --> 00:03:32,365
path. So that's the implementation of the
two query method. So, now what we're want,

35
00:03:32,365 --> 00:03:38,392
we're going to want to talk about for the
rest of the lecture is the algorithms that

36
00:03:38,392 --> 00:03:44,474
build these data structures. Now, all of
the algorithms that we look at are based

37
00:03:44,474 --> 00:03:51,154
on a concept called relaxation or edge
relaxation. So, now recall that our data

38
00:03:51,154 --> 00:03:57,988
structure. So we're gonna talk about
relaxing an edge from v to w and we have

39
00:03:57,988 --> 00:04:04,350
an example here, from v to w. and at the
point that we're gonna relax this edge.

40
00:04:04,594 --> 00:04:12,009
we'll , have our data structures in
process in this too. We haven't seen all

41
00:04:12,009 --> 00:04:18,121
edges. We haven't seen all passes, paths
in the intermediate part of some

42
00:04:18,121 --> 00:04:24,885
algorithm. So, but we'll try to make sure
that this 2v for every vertex is the

43
00:04:24,885 --> 00:04:31,567
length of the shortest known path to that
vertex. And that's gonna be the same for

44
00:04:31,567 --> 00:04:38,355
W. So, these are all the edges that are in
Edge two that we know pass from some S to

45
00:04:38,355 --> 00:04:45,308
some vertex. so this 2v and this 2w will
contain its shortest known path. Now, if

46
00:04:45,308 --> 00:04:52,997
we in also Edge 2wv is the. Edge 2w is the
last edge in the shortest known path from

47
00:04:52,997 --> 00:04:58,233
s to w. and the same way with extra v of
course. Now, so to relax along the edge

48
00:04:58,233 --> 00:05:03,750
from v to w, essentially that means, let's
update the data structures to take that

49
00:05:03,750 --> 00:05:08,940
edge to an, into account. And what happens
in this case is that the edge gives a

50
00:05:08,940 --> 00:05:14,571
better way to get to w so that's what
relaxing is. that edge gives us a new

51
00:05:14,571 --> 00:05:20,491
shortest pass so we want to include it in
the data structure. So since it has a

52
00:05:20,491 --> 00:05:26,483
shorte r path, we have to update both,
disc 2w and edge 2Ww That is, we have a

53
00:05:26,483 --> 00:05:32,518
new way to get to W. So we have to throw
away, throw away that old edge that came

54
00:05:32,518 --> 00:05:39,080
to w and we have, a new shorter distance.
Instead of 7.2 that came that old way, we

55
00:05:39,080 --> 00:05:45,492
have 4.4 that gets us, a new way. So edge
relaxation, is a very natural operation.

56
00:05:45,492 --> 00:05:51,753
When we consider a new edge, does it give
a new shortest path to that vertex or not?

57
00:05:51,753 --> 00:05:58,034
If it doesn't, we ignore it. If it does we
update the data structures to include that

58
00:05:58,034 --> 00:06:04,067
edge and forget about the old edge that to
took us, took us to that vertex. That's

59
00:06:04,067 --> 00:06:09,876
edge relaxation. And this is, easy
implementation of edge relaxation in code.

60
00:06:09,876 --> 00:06:16,462
So to relax and edge. we pull out its
front and two vertices in VNW according to

61
00:06:16,462 --> 00:06:22,566
our standard idiom, and then we just see
if the distance to w that's, what's the

62
00:06:22,566 --> 00:06:29,674
shortest path before, is bigger than the
distance to v plus the weight of the edge

63
00:06:29,674 --> 00:06:36,010
that would take us from v to w if it's
bigger, that means we've found a new path.

64
00:06:36,010 --> 00:06:41,344
If it's less than or equal we ignore it.
And if we found a new path we have to

65
00:06:41,344 --> 00:06:46,611
update the distance to w to be the new
distance. Distance to v plus follow VW.

66
00:06:46,611 --> 00:06:52,014
And then we have to update edge 2w and
throw away the old version and say that

67
00:06:52,014 --> 00:06:57,716
our new edge from v to w is the best path
to w as far as we know. So that's easy

68
00:06:57,716 --> 00:07:04,705
code for edge relaxation. Now we're gonna
use edge relaxation in a really

69
00:07:04,705 --> 00:07:13,373
fundamental way to compute shortest paths,
but there's one other important idea which

70
00:07:13,373 --> 00:07:21,531
is called optimality conditions, and this
is a way to know that we have shortest

71
00:07:21,531 --> 00:07:28,772
paths, and we have computed all the
shortest paths, so the shortest path,

72
00:07:28,772 --> 00:07:35,384
optimality conditions, are is embodied in
the, in this proposition, so we have an

73
00:07:35,384 --> 00:07:41,929
edge way to diagraph. and we have the this
two array. Let's just talk about the

74
00:07:41,929 --> 00:07:48,910
distances and path go with the distances.
But the key point is that this two array

75
00:07:48,910 --> 00:07:55,277
represents the shortest path distances
from the given source s, if and only if

76
00:07:55,277 --> 00:08:01,562
these two conditions hold. So the first
thing is, if its the length for every

77
00:08:01,562 --> 00:08:08,667
vertex, this 2v is the length of some path
from s to the vertex, and our algorithm

78
00:08:08,667 --> 00:08:14,663
always try to ensure, will, always ensures
that. And then, the second thing is for

79
00:08:14,663 --> 00:08:22,642
every edge, vw We have this condition
that, that this 2w that we, have stored is

80
00:08:22,642 --> 00:08:28,906
less than or equal to this 2v, plus the
weight at the edge from v to w. That's the

81
00:08:28,906 --> 00:08:36,088
shortest path optimality conditions. if,
they're equal, So sometimes, they'll be

82
00:08:36,088 --> 00:08:42,542
equal. for example, if vw is the last edge
on the shortest path. and sometimes, it

83
00:08:42,542 --> 00:08:47,075
would be great if it, it, never been
smaller, and never be way to get the W

84
00:08:47,075 --> 00:08:52,272
that we haven't found. That's the shortest
path, optimality conditions. and again,

85
00:08:52,508 --> 00:08:59,270
just a quick proof although best way to
understand proof is that we've been slowly

86
00:08:59,506 --> 00:09:06,180
now listen to them, spoken quickly, but
I'll quickly outline them. so here is the,

87
00:09:06,425 --> 00:09:13,634
the necessary suppose that so, so we wanna
prove that if, if this is true then we

88
00:09:13,634 --> 00:09:20,269
have shortest paths. So to do that we
assume the contrary. Suppose that the

89
00:09:20,269 --> 00:09:27,477
distance to w is bigger than the distance
to b + e that way for some edge. Then that

90
00:09:27,477 --> 00:09:34,128
path is gonna give a path to w that's
shorter than distance w cause v is the

91
00:09:34,128 --> 00:09:41,825
path and the wait's shorter. in that is a
contradiction to the idea that you have

92
00:09:41,825 --> 00:09:50,848
shortest paths so there can't be any, such
edge where that condition holds. so that's

93
00:09:50,848 --> 00:09:58,456
necessary and then sufficient. Suppose
that we have shortest path from s to w.

94
00:09:58,722 --> 00:10:09,353
then Now we're assuming these conditions
all hold. then, For every edge on the path

95
00:10:09,591 --> 00:10:16,259
this has to all hold. so, so, for, it
starts at the end. so, the distance to the

96
00:10:16,259 --> 00:10:23,006
last edge goes from VK - one to VK. So
distance to VK is less than or equal to

97
00:10:23,006 --> 00:10:30,151
the distance to VK - one plus the weight
of the Kth edge. and so just continuing

98
00:10:30,151 --> 00:10:37,295
down that way then from the source to the
first edge, but it's a source plus the

99
00:10:37,295 --> 00:10:43,405
weight of the first edge is greater or
equal distance to the first vertex after

100
00:10:43,405 --> 00:10:49,467
the source, and all those conditions have
to old. And then, what we can do is just

101
00:10:49,691 --> 00:10:57,296
add up all those weights. and simplify it.
But and then that shows that the distance

102
00:10:57,296 --> 00:11:03,321
to w is equal to the length of the
shortest path. an d so it's gotta be the

103
00:11:03,321 --> 00:11:09,345
weight of the shortest path. Because it's
the weight of some path and it's got that

104
00:11:09,345 --> 00:11:15,442
weight, it's gotta be the weight of the
shortest path. so if those conditions hold

105
00:11:15,660 --> 00:11:21,824
we have shortest paths. So our the, the
point of this proof, it's a slightly

106
00:11:21,824 --> 00:11:28,449
complicated proof, but it's not too bad,
it's quite natural is that all we have to

107
00:11:28,449 --> 00:11:35,087
know to w-, check that we have computed
shortest path. These are these optimality

108
00:11:35,087 --> 00:11:39,573
conditions hold, to prove that an
algorithm computes shortest paths. We just

109
00:11:39,573 --> 00:11:44,366
have to prove that it ends up with the
optimality conditions and force, and

110
00:11:44,366 --> 00:11:48,863
that's what we'll be doing. And the
optimality condition, really, it's just

111
00:11:48,863 --> 00:11:56,417
saying that there's no edge there that we
missed. Okay so with that idea, in fact

112
00:11:56,417 --> 00:12:04,577
there's a very simple, easy to state,
generic algorithm that is going to compute

113
00:12:04,577 --> 00:12:10,917
shortest paths. and it's very simple. We
start with the distance to the source

114
00:12:11,141 --> 00:12:17,555
being zero And the distance to every other
vertex infinity. And all we do is repeat

115
00:12:17,555 --> 00:12:23,148
until the optimality conditions are
satisfied, relax any edge. Just go ahead

116
00:12:23,148 --> 00:12:28,906
and relax edges until the optimality
conditions are satisfied. So, That's a

117
00:12:28,906 --> 00:12:35,461
very general algorithm. We don't say how
to decide which edge to, relax or how to

118
00:12:35,461 --> 00:12:41,254
know the optimality conditions are
satisfied. But still, it's, quite an

119
00:12:41,254 --> 00:12:47,580
amazingly simple generic algorithm. so,
how do we know, how can we show that it

120
00:12:47,580 --> 00:12:53,914
computes the SBT? Well it's pretty simple.
throughout the algorithm. We're making

121
00:12:53,914 --> 00:13:00,772
sure that because of the way that we do
relax edges the distance to V is the

122
00:13:00,772 --> 00:13:05,896
length of a simple path from S to V, and
edge s to v is the length of a simple path

123
00:13:05,896 --> 00:13:09,697
from s to v and edge to v is the last edge
on that path That's what relaxation does

124
00:13:09,945 --> 00:13:16,886
for any vertex that we touch. and not only
that, every relaxation that succeeds

125
00:13:16,886 --> 00:13:23,180
decreases the distances. and we've assumed
that there's a way to get to every, every

126
00:13:23,180 --> 00:13:29,289
vertex. and there's only a finite number
for paths. So it can decrease, at most, a

127
00:13:29,289 --> 00:13:37,158
finite number of times. So it's going to,
the algorithm's gonna terminate. It's as

128
00:13:37,158 --> 00:13:44,553
simple as that. A gain, this is a little
bit of a mind blowing concept. But we'll

129
00:13:44,553 --> 00:13:52,611
leave that for more careful study and just
for now realize that all we have to do is

130
00:13:52,611 --> 00:13:59,645
relax along edges. And what we're going to
do now is look at. Different ways of

131
00:13:59,645 --> 00:14:05,446
figuring out how to choose which edge to
relax. The first algorithm that we'll look

132
00:14:05,446 --> 00:14:10,210
at is a classic algorithm known as
Dijkstra's algorithm one of the most

133
00:14:10,210 --> 00:14:15,165
famous of all algorithms. and that is
effective when the weights are non

134
00:14:15,165 --> 00:14:20,755
negative. then we'll look at an algorithm
that works even with negative weights as

135
00:14:20,755 --> 00:14:26,180
long as there aren't any directed cycles.
and then we'll look at an even older

136
00:14:26,180 --> 00:14:32,244
algorithm than Dykstra's, the Bellman-Ford
algorithm. that can, solve the shortest

137
00:14:32,244 --> 00:14:38,026
path, problem and graphs with negative
weights, as long as there's, no negative