1
00:00:01,300 --> 00:00:06,300
- Okay, so here we are
week 13 of CS124 online,

2
00:00:06,600 --> 00:00:08,613
Data Structures and Algorithms.

3
00:00:09,520 --> 00:00:13,663
And last week we wrapped up the
dynamic equivalence problem.

4
00:00:14,680 --> 00:00:18,170
We introduced graphs and we
saw our first graph algorithm,

5
00:00:18,170 --> 00:00:20,420
which was topological sort.

6
00:00:20,420 --> 00:00:23,540
And this week we've got
some really cool stuff.

7
00:00:23,540 --> 00:00:27,440
So we'll see how to find the
shortest paths in a graph.

8
00:00:27,440 --> 00:00:31,010
So if we have some graph, with
all these nodes and edges,

9
00:00:31,010 --> 00:00:35,100
we're gonna be able to pick a
particular node in that graph

10
00:00:35,100 --> 00:00:37,330
and find the shortest
path through the graph,

11
00:00:37,330 --> 00:00:38,873
no matter how complex it is,

12
00:00:40,290 --> 00:00:42,220
to all the other nodes in the graph.

13
00:00:42,220 --> 00:00:43,830
And we're gonna do this using

14
00:00:43,830 --> 00:00:46,330
what's called Dijkstra's algorithm,

15
00:00:46,330 --> 00:00:49,830
one of the most famous
algorithms in computer science.

16
00:00:49,830 --> 00:00:53,070
And Dijkstra's algorithm
uses a greedy approach

17
00:00:53,070 --> 00:00:54,620
to find these paths.

18
00:00:54,620 --> 00:00:58,640
And it works as long as there
are no negative edge weights

19
00:00:58,640 --> 00:00:59,720
in the graph.

20
00:00:59,720 --> 00:01:02,660
So if we have a negative edge weight,

21
00:01:02,660 --> 00:01:04,510
which is reasonable thing to have

22
00:01:04,510 --> 00:01:07,120
in a number of different
kinds of problems,

23
00:01:07,120 --> 00:01:09,520
then Dijkstra's no longer works.

24
00:01:09,520 --> 00:01:12,630
And so what we'll learn
is to handle graphs

25
00:01:12,630 --> 00:01:17,560
with negative weight edges
but no negative weight cycles.

26
00:01:17,560 --> 00:01:20,173
We'll use what's called
the Bellman-Ford algorithm.

27
00:01:21,030 --> 00:01:24,070
And the Bellman-Ford algorithm
is very much like Dijkstra's

28
00:01:24,070 --> 00:01:26,260
and so it makes sense to
present the two together.

29
00:01:26,260 --> 00:01:29,610
So we'll see they're very, very
similar kinds of algorithms.

30
00:01:29,610 --> 00:01:31,473
There's just a few differences.

31
00:01:32,380 --> 00:01:35,860
And after exploring these
shortest path algorithms,

32
00:01:35,860 --> 00:01:38,250
we'll look at what are
called network flows

33
00:01:38,250 --> 00:01:41,770
where we have networks that are
represented by these graphs.

34
00:01:41,770 --> 00:01:44,880
And we wanna find the maximum flow

35
00:01:44,880 --> 00:01:49,757
that can flow through the
network from some node

36
00:01:50,720 --> 00:01:54,370
that we designate as the
source to some other node

37
00:01:54,370 --> 00:01:56,120
that we designate as the sync.

38
00:01:56,120 --> 00:01:58,930
And the weights, these are
weighted directed graphs

39
00:01:58,930 --> 00:02:02,780
that we'll be looking at and
the weights in these graphs,

40
00:02:02,780 --> 00:02:05,520
these networks, represents the capacity

41
00:02:05,520 --> 00:02:07,523
that can flow along each edge.

42
00:02:08,380 --> 00:02:10,710
So we're designating
one node as the source,

43
00:02:10,710 --> 00:02:12,870
one is the sync, and it turns out

44
00:02:12,870 --> 00:02:16,430
that finding the maximum flow
through a network like this

45
00:02:16,430 --> 00:02:18,050
is equivalent to finding what's called

46
00:02:18,050 --> 00:02:20,380
the minimum cut through the network,

47
00:02:20,380 --> 00:02:23,710
and you'll hear the term max-flow min-cut.

48
00:02:23,710 --> 00:02:26,820
And a cut is where we have some graph

49
00:02:26,820 --> 00:02:30,660
and we remove a subset of the edges

50
00:02:30,660 --> 00:02:33,340
so that we disconnect the graph

51
00:02:33,340 --> 00:02:36,440
into two disconnected components.

52
00:02:36,440 --> 00:02:40,340
So if we have the source
and we have the sync,

53
00:02:40,340 --> 00:02:43,300
a cut is where we remove a subset

54
00:02:43,300 --> 00:02:46,840
of the edges in the connected
graph in the network

55
00:02:46,840 --> 00:02:49,470
to separate the source and the sync.

56
00:02:49,470 --> 00:02:50,970
We're only concerned about cuts

57
00:02:50,970 --> 00:02:53,560
that separate the source and the sync

58
00:02:53,560 --> 00:02:58,123
into two, as elements in
two disconnect components.

59
00:02:59,080 --> 00:03:02,370
And whenever flow through a network,

60
00:03:02,370 --> 00:03:04,630
whenever we have flow through a network,

61
00:03:04,630 --> 00:03:07,660
it's gotta flow through at
least some of those edges

62
00:03:07,660 --> 00:03:11,050
in the cut in the graph,
because of the sync's over here,

63
00:03:11,050 --> 00:03:12,550
the source is over here,

64
00:03:12,550 --> 00:03:14,930
and it's gotta go through
some of those edges

65
00:03:14,930 --> 00:03:19,030
that we removed to produce the cut.

66
00:03:19,030 --> 00:03:22,440
So if we can find some cut in the network

67
00:03:22,440 --> 00:03:25,110
with some sum of the weights of the edges,

68
00:03:25,110 --> 00:03:26,720
which are the capacities,

69
00:03:26,720 --> 00:03:30,000
we take the sum of the weights
of the edges that we remove,

70
00:03:30,000 --> 00:03:32,850
we certainly can't have
flow through the network

71
00:03:32,850 --> 00:03:35,940
that exceeds the value of such a cut.

72
00:03:35,940 --> 00:03:39,820
So maximum flow and
minimum cut are two sides

73
00:03:39,820 --> 00:03:40,930
of the same coin.

74
00:03:40,930 --> 00:03:43,069
The maximum flow through a network

75
00:03:43,069 --> 00:03:46,000
is the same value as the minimum cut

76
00:03:46,000 --> 00:03:48,510
that we can find through the same network

77
00:03:48,510 --> 00:03:50,963
that separates the source from the sync.

78
00:03:52,240 --> 00:03:56,190
And to solve the problem of
finding the maximum flow,

79
00:03:56,190 --> 00:03:58,610
we'll learn about the Ford-Fulkerson

80
00:03:58,610 --> 00:04:01,180
and Edmonds-Karp algorithms.

81
00:04:01,180 --> 00:04:05,640
And these also, like
Dijkstra's and Bellman Ford,

82
00:04:05,640 --> 00:04:08,420
take a greedy approach,
finding the maximum flow

83
00:04:08,420 --> 00:04:13,190
by iterating and finding what
are called augmenting paths,

84
00:04:13,190 --> 00:04:15,990
which is a path from
the source to the sync

85
00:04:15,990 --> 00:04:17,943
that still has some capacity on it.

86
00:04:18,840 --> 00:04:22,570
And the flow supported
by each augmenting path

87
00:04:22,570 --> 00:04:25,920
is added to the solution
in a greedy fashion,

88
00:04:25,920 --> 00:04:29,460
until we can find no more
augmenting paths in the network.

89
00:04:29,460 --> 00:04:30,300
And once we do,

90
00:04:30,300 --> 00:04:35,130
then that's supposedly gonna
give us the the maximum flow.

91
00:04:35,130 --> 00:04:37,760
But we'll see, there's a
gotcha. There's a gotcha.

92
00:04:37,760 --> 00:04:39,770
And it's possible to find

93
00:04:39,770 --> 00:04:43,230
a bad sequence of augmenting paths,

94
00:04:43,230 --> 00:04:44,900
but with a little trick

95
00:04:44,900 --> 00:04:47,283
we'll show how we can
resolve that problem.

96
00:04:48,690 --> 00:04:53,423
And so that's Ford-Fulkerson
and Edmonds Karp.

97
00:04:54,360 --> 00:04:57,520
And I think the best way
to learn these algorithms

98
00:04:57,520 --> 00:05:00,600
is to actually work through
some examples yourself

99
00:05:00,600 --> 00:05:02,150
with pencil and paper.

100
00:05:02,150 --> 00:05:05,650
So I'm gonna provide some
problems for practice.

101
00:05:05,650 --> 00:05:07,330
And the smart money says

102
00:05:07,330 --> 00:05:11,840
that there will be problems
like these on the final exam.

103
00:05:11,840 --> 00:05:16,170
So we're definitely gonna
touch on these algorithms

104
00:05:16,170 --> 00:05:17,090
on the final exam.

105
00:05:17,090 --> 00:05:20,190
So a little practice
will be good preparation.

106
00:05:20,190 --> 00:05:22,350
And then here's the part of the spiel

107
00:05:22,350 --> 00:05:24,160
that's always the same every week.

108
00:05:24,160 --> 00:05:27,570
At the end of the week we're
gonna have another quiz

109
00:05:27,570 --> 00:05:30,090
running from Thursday to Sunday.

110
00:05:30,090 --> 00:05:32,000
It'll cover this week's material

111
00:05:32,000 --> 00:05:36,410
and a little bit of material
from what we covered last week.

112
00:05:36,410 --> 00:05:37,860
So that's all for now

113
00:05:37,860 --> 00:05:41,490
and I'll see you on our
Yellowdig Discussion Board.

114
00:05:41,490 --> 00:05:42,323
Bye bye.