1
00:00:01,900 --> 00:00:05,710
Today we're going to talk about shortest
path algorithm.

2
00:00:05,710 --> 00:00:10,079
This was another problem on graph that's
very easy to, to state.

3
00:00:10,294 --> 00:00:13,589
We use, again, a slightly different graph
model.

4
00:00:13,804 --> 00:00:19,176
Last time, we had edge-weighted graphs for
computing minimum spanning trees.

5
00:00:19,176 --> 00:00:22,830
Now, we're going to have edge-weighted
directed graphs.

6
00:00:22,830 --> 00:00:26,297
So now the edges are directed, but they're
weighted.

7
00:00:26,297 --> 00:00:31,176
And the problem that we're going to be
looking at is to find the shortest path

8
00:00:31,176 --> 00:00:35,718
from one vertex to another.
So in this example, we've got a directed

9
00:00:35,718 --> 00:00:39,159
graph with a variety of edges, the
directed edges.

10
00:00:39,159 --> 00:00:44,075
And our goal is to find given two
vertices, say zero to six, what's the

11
00:00:44,075 --> 00:00:47,232
shortest path that takes us from zero to
six.

12
00:00:47,235 --> 00:00:51,167
Where the length of the path is the sum of
it's weights.

13
00:00:51,167 --> 00:00:56,637
And in this case, the shortest distance
from zero to two, two to seven, seven to

14
00:00:56,637 --> 00:01:00,695
three, and three to six.
Now, the algorithms that we're going to

15
00:01:00,695 --> 00:01:06,189
look at for this are classic algorithms
and this is an example where years ago we

16
00:01:06,189 --> 00:01:10,229
would teach these algorithms,
Algorithms and say, well, they will be

17
00:01:10,229 --> 00:01:14,147
important someday,
When people have devices, with maps on

18
00:01:14,147 --> 00:01:18,064
them and will want to get around.
Nowadays, of course, everyone's familiar

19
00:01:18,064 --> 00:01:22,403
with these kinds of devices.
When you have a map and you want to get

20
00:01:22,403 --> 00:01:27,224
from one place to another or you have, a
device, in your car that gives you

21
00:01:27,224 --> 00:01:29,876
directions to get from one place to
another.

22
00:01:29,876 --> 00:01:34,818
These devices are implementing the classic
algorithms that we're going to talk about

23
00:01:34,818 --> 00:01:38,335
today.
Not only that and even more important,

24
00:01:38,335 --> 00:01:44,647
shortest path is a really interesting and
important problem solving model. There's

25
00:01:44,647 --> 00:01:50,337
all kinds of important practical problems
that can be recast as shortest paths

26
00:01:50,337 --> 00:01:53,790
problems.
And because we have efficient solutions to

27
00:01:53,790 --> 00:01:58,903
the shortest path, efficient algorithms
for finding shortest paths, we have

28
00:01:58,903 --> 00:02:02,290
efficient solutions to all these kinds of
problems,

29
00:02:02,556 --> 00:02:07,358
All around us.
From texture mapping, to network routing

30
00:02:07,358 --> 00:02:14,737
protocols, to pipelining, to trucks, to
traffic planning, we find shortest path

31
00:02:15,004 --> 00:02:21,940
applications and we'll look at a couple
surprising examples later on today.

32
00:02:21,940 --> 00:02:27,954
So one thing to think about is, let's
specify really what the problem's all

33
00:02:27,954 --> 00:02:33,157
about a this all different variance,
similar to many other problems we've

34
00:02:33,157 --> 00:02:36,359
studied.
So one thing is, what vertices are we

35
00:02:36,359 --> 00:02:39,761
talking about?
So, of course, the most familiar is

36
00:02:39,761 --> 00:02:44,163
so-called source-sink.
What's the shortest path from one vertex

37
00:02:44,163 --> 00:02:47,298
to another?
But actually, more useful often is

38
00:02:47,298 --> 00:02:53,174
so-called single source shortest path,
which is all the paths from one vertex to

39
00:02:53,174 --> 00:02:56,918
every other.
And this is the one for example that the

40
00:02:56,918 --> 00:03:02,280
navigation system in your car might use.
The source is where you are and it'll

41
00:03:02,280 --> 00:03:05,344
compute the shortest paths to every place
else.

42
00:03:05,344 --> 00:03:10,450
And then when you ask for some place it'll
just pick the one that you want in a

43
00:03:10,450 --> 00:03:14,600
manner very similar to the API that we're
going to talk about.

44
00:03:14,600 --> 00:03:20,300
Another thing that you might do if you
didn't have that many vertices is compute

45
00:03:20,300 --> 00:03:25,253
all pairs of shortest paths.
So, precompute the path between all pairs

46
00:03:25,253 --> 00:03:29,325
of vertices.
And then immediately be able to direct

47
00:03:29,732 --> 00:03:34,211
answer a client query.
This is the type of thing that was used on

48
00:03:34,211 --> 00:03:39,792
the old map, for example.
Another thing is the edge-weights.

49
00:03:39,792 --> 00:03:45,114
Usually, we think of it in terms of
positive edge-weights cuz the maps are

50
00:03:45,114 --> 00:03:50,841
geometric and so the length of an edge is
proportional to it's distance in the

51
00:03:50,841 --> 00:03:54,613
plane.
But, actually for many problems there may

52
00:03:54,613 --> 00:04:01,081
be much more arbitrary and actually one of
the big issues that we'll see is whether

53
00:04:01,081 --> 00:04:04,449
the eggs, edge-weights are positive or
negative.

54
00:04:04,651 --> 00:04:09,838
And those types of restrictions are going
to give rise to different types of

55
00:04:09,838 --> 00:04:12,649
algorithms.
Another issue that arises and is

56
00:04:12,649 --> 00:04:16,848
particular important in the presence of
negative weights that we'll see at the

57
00:04:16,848 --> 00:04:19,465
end,
Is weather or not the graph, graph has

58
00:04:19,465 --> 00:04:23,865
directive cycles.
In particular whether the total length of

59
00:04:23,865 --> 00:04:28,576
a cycle is negative or not and we'll get
to that at the end.

60
00:04:28,576 --> 00:04:34,633
So, and also, just to reduce some clutter
in our code in the slides, we'll

61
00:04:34,858 --> 00:04:40,093
throughout the lecture, make the
simplifying assumption that there are

62
00:04:40,093 --> 00:04:46,150
paths from the source to every vertex.
We won't worry about driving to islands

63
00:04:46,150 --> 00:04:51,401
and other such issue.
To get started, we have to develop our

64
00:04:51,401 --> 00:04:55,081
APIs.
And this'll be straightforward after cuz

65
00:04:55,081 --> 00:04:59,326
this is the fourth variation of a graph
API that we've done.

66
00:04:59,326 --> 00:05:02,511
We started with, regular undirected
graphs,

67
00:05:02,511 --> 00:05:06,190
Then we did digraphs,
Then we did weighted, graphs,

68
00:05:06,190 --> 00:05:12,368
And, now, we're doing weighted digraphs.
So to begin, we're going to need a API for

69
00:05:12,368 --> 00:05:17,352
processing edges.
And this is actually simpler for digraphs

70
00:05:17,352 --> 00:05:23,831
than it was for undirected graphs,
Cuz we have this concept of one of the

71
00:05:23,831 --> 00:05:29,646
vertices is, where the edge goes from and
the other vertex is where, is where it

72
00:05:29,646 --> 00:05:33,799
goes to.
So we have our constructor that builds an

73
00:05:33,799 --> 00:05:36,703
edge from,
The vertex that's given it's first

74
00:05:36,703 --> 00:05:41,500
argument to the vertex that's given it's
second argument and there's a double list

75
00:05:41,500 --> 00:05:44,995
of weight.
And then, the client can ask for the from

76
00:05:44,995 --> 00:05:48,786
vertex or the to vertex or the weight or
string representation.

77
00:05:48,964 --> 00:05:53,999
And always in our code we'll use the idiom
at the bottom of the slide for processing

78
00:05:53,999 --> 00:05:57,019
an edge.
We'll pick out v which is e.from and w

79
00:05:57,019 --> 00:06:00,100
which is e.2 and then our code will
process v and w.

80
00:06:00,339 --> 00:06:06,564
The implementation of a weighted directed
edge is very similar to the one for

81
00:06:06,564 --> 00:06:13,347
undirected graphs, but simpler,
Because, the, constructor, simply sets the

82
00:06:13,347 --> 00:06:20,643
instance variables from its argument,
And from and to are simply getter methods

83
00:06:20,933 --> 00:06:26,531
as is weight.
So that's implementation of directed edge

84
00:06:26,531 --> 00:06:32,496
for directed weighted graphs.
So now what about the graph itself?

85
00:06:32,496 --> 00:06:37,943
So, edge-weighted digraph.
So, as usual, we have a constructor, that

86
00:06:37,943 --> 00:06:41,421
gives, that takes the number of vertices
in the graph,

87
00:06:41,421 --> 00:06:45,950
So we can build data structures that are
vertex, vertex index arrays.

88
00:06:46,167 --> 00:06:51,957
Or we can reterminate the input stream.
And then the key methods are add edge,

89
00:06:51,957 --> 00:06:55,866
which takes in directed edge and adds it
to the graph.

90
00:06:56,083 --> 00:07:03,222
And then the Iterable per adjacency list,
which returns an Iterable of all the edges

91
00:07:03,222 --> 00:07:09,488
that point from a given vertex.
So since we're processing edges, we can

92
00:07:09,488 --> 00:07:16,002
have self loops and parallel edges and
most of our code will simply use adj

93
00:07:16,002 --> 00:07:20,950
method to iterate through the edges
adjacent to vertices.

94
00:07:21,814 --> 00:07:28,262
Representation, is very similar to the
other representations, that we've seen,

95
00:07:28,498 --> 00:07:32,823
except simpler,
Because it's only one representation of

96
00:07:32,823 --> 00:07:38,829
each edge.
So, there's a, the, instance variable for

97
00:07:38,829 --> 00:07:42,938
the adjacency list is a vertex index
array.

98
00:07:42,938 --> 00:07:49,480
Each entry is a bag of directed edges,
actually, references to directed edges.

99
00:07:49,480 --> 00:07:56,831
So, the, all the code for, building and
processing this is very straightforward

100
00:07:56,831 --> 00:08:03,473
version of code that we've seen before.
Here's the implementation, for,

101
00:08:04,182 --> 00:08:09,496
edge-weighted digraphs.
It's the, the same as our edge-weighted

102
00:08:09,496 --> 00:08:15,518
graph, except, we just replace graph with
digraph, everywhere.

103
00:08:15,784 --> 00:08:22,870
And, when we add an edge, we only add it
to the from vertices adjacency list.

104
00:08:22,870 --> 00:08:26,955
So v is e.from, adj v equals add, add the
edge to that.

105
00:08:27,166 --> 00:08:33,224
And then to get all the vertices adjacent
to a given vertex we just re-used the

106
00:08:33,224 --> 00:08:38,507
vertex array just to get its adjacency
list and return that bag which is

107
00:08:38,507 --> 00:08:42,381
Iterable,
So that the client can iterate through all

108
00:08:42,381 --> 00:08:46,607
those vertices.
A very straightforward version of what we

109
00:08:46,607 --> 00:08:49,405
did for edge-weighted graphs.
Okay,

110
00:08:49,405 --> 00:08:56,769
So now, our client for that program is,
our single source shortest paths, API.

111
00:08:57,052 --> 00:09:04,983
And so, it works in a manner very similar
to others that we've done and we'll call

112
00:09:04,983 --> 00:09:09,609
it SP.
The constructor takes a graph and a source

113
00:09:09,609 --> 00:09:12,934
vertex and it'll go ahead and build the
data structures.

114
00:09:12,934 --> 00:09:17,012
It'll find the shortest path from the
short, from s vertext to every other

115
00:09:17,012 --> 00:09:22,618
vertex in the graph and build the data
structures, so that it can efficiently

116
00:09:22,618 --> 00:09:28,960
answer client queries of, first, what's
the length of the shortest path from s to

117
00:09:28,960 --> 00:09:32,290
a given vertex? And second, what's the
path,

118
00:09:32,290 --> 00:09:38,315
Give, an, an iterable that gives the path
from the source vertex, from the source

119
00:09:38,315 --> 00:09:43,626
vertex to the given vertex?
So this test client here will print out

120
00:09:43,626 --> 00:09:50,303
all the shortest paths from the given
vertex s to every other vertex in the

121
00:09:50,303 --> 00:09:55,700
graph. Go through all the vertices.
For every vertex,

122
00:09:56,178 --> 00:10:01,840
You print s to v and the distance from s
to v.

123
00:10:01,840 --> 00:10:06,455
And then for every edge in the path, you
simply print out the edge,

124
00:10:06,455 --> 00:10:12,190
So it'll print for every vertex, the
distance from s to that vertex followed by

125
00:10:12,190 --> 00:10:16,677
the path.
So, for example for the sample graph that

126
00:10:16,677 --> 00:10:23,736
we gave with vertex zero as the source
it'll print out the path from zero to

127
00:10:23,736 --> 00:10:29,809
every vertex in the graph.
So that's a test client that we'll use to

128
00:10:30,055 --> 00:10:35,555
make sure to check and learn the operation
of our algorithms.

129
00:10:35,801 --> 00:10:40,889
And this API is going to be effective even
for huge graphs.

130
00:10:40,889 --> 00:10:45,240
So that's and introduction to our shortest
paths API.