1 00:00:00,840 --> 00:00:02,130 - [Instructor] Hello there. 2 00:00:02,130 --> 00:00:04,383 Okay, now we're gonna do network flows. 3 00:00:05,400 --> 00:00:08,110 An important application of graph algorithms 4 00:00:08,110 --> 00:00:11,320 is what's called network flow, 5 00:00:11,320 --> 00:00:13,730 and the first example that we usually see 6 00:00:13,730 --> 00:00:15,540 when talking about network flows 7 00:00:15,540 --> 00:00:19,710 is in finding the maximum flow through a network. 8 00:00:19,710 --> 00:00:21,130 Well, what's a network? 9 00:00:21,130 --> 00:00:23,790 Well, there are all kinds of networks. 10 00:00:23,790 --> 00:00:25,510 There are transportation networks 11 00:00:25,510 --> 00:00:27,153 like the London Underground, 12 00:00:28,320 --> 00:00:31,553 or global fiber optic networks, 13 00:00:32,880 --> 00:00:37,880 or national electric grids, natural gas pipelines, 14 00:00:40,930 --> 00:00:42,800 or chemical reaction networks. 15 00:00:42,800 --> 00:00:46,860 And in each case, it's a natural question to ask, 16 00:00:46,860 --> 00:00:49,380 and often a very useful question to ask, 17 00:00:49,380 --> 00:00:52,670 what's the maximum flow through the network? 18 00:00:52,670 --> 00:00:55,240 What's the maximum flow that the network can support, 19 00:00:55,240 --> 00:00:59,090 whether that's of trains, of data packets, of amps, 20 00:00:59,090 --> 00:01:02,423 of cubic meters of natural gas, of reactions, whatever? 21 00:01:03,770 --> 00:01:06,900 So it's reasonable to ask, 22 00:01:06,900 --> 00:01:09,050 what's the maximum flow of trains 23 00:01:09,050 --> 00:01:11,063 between Bond Street and Whitechapel? 24 00:01:12,690 --> 00:01:15,150 How many megabits per second can flow 25 00:01:15,150 --> 00:01:20,150 between Jacksonville here and Mumbai over here? 26 00:01:22,890 --> 00:01:26,663 How much electricity can flow from Louisiana to Chicago? 27 00:01:28,830 --> 00:01:31,800 How many cubic meters of gas can flow per day 28 00:01:31,800 --> 00:01:34,340 between natural gas fields in Siberia 29 00:01:34,340 --> 00:01:36,083 and consumers in Amsterdam? 30 00:01:38,100 --> 00:01:40,500 And given some precursor chemical, 31 00:01:40,500 --> 00:01:43,410 at what rate can we produce some reaction product? 32 00:01:43,410 --> 00:01:44,243 And so on. 33 00:01:45,420 --> 00:01:48,560 So let's start with a really simple network. 34 00:01:48,560 --> 00:01:51,640 This is a really simple network. 35 00:01:51,640 --> 00:01:54,200 So here we have a directed graph, 36 00:01:54,200 --> 00:01:58,240 and let's call s the source, 37 00:01:58,240 --> 00:02:01,120 and we'll call t the sink. 38 00:02:01,120 --> 00:02:04,840 And a flow through the network originates at the source 39 00:02:04,840 --> 00:02:06,463 and ends up at the sink. 40 00:02:07,970 --> 00:02:10,610 Again, this flow could be trains or data packets 41 00:02:10,610 --> 00:02:13,420 or electricity or natural gas or water, 42 00:02:13,420 --> 00:02:15,840 anything that can flow through a network, 43 00:02:15,840 --> 00:02:18,480 although it is common for us to think of network flows 44 00:02:18,480 --> 00:02:21,903 by using an analogy with the flow of fluid, okay? 45 00:02:23,150 --> 00:02:26,530 And each edge in the network has weight, 46 00:02:26,530 --> 00:02:28,510 and that's called its capacity. 47 00:02:28,510 --> 00:02:32,480 So here we have a capacity of two units 48 00:02:32,480 --> 00:02:36,840 from the source s to this node x, 49 00:02:36,840 --> 00:02:41,840 and a capacity of one unit from this node x to the sink t. 50 00:02:45,080 --> 00:02:48,300 So what exactly is a flow, then? 51 00:02:48,300 --> 00:02:50,303 Let's make this a little more precise. 52 00:02:54,720 --> 00:02:59,720 We write f sub u, v to be the flow from u to v. 53 00:03:00,510 --> 00:03:04,660 So if we have two nodes, one labeled u, one labeled v, 54 00:03:04,660 --> 00:03:09,573 F sub u, v is the flow between those two, okay? 55 00:03:11,120 --> 00:03:13,100 And we have some constraints on flows. 56 00:03:13,100 --> 00:03:17,650 So the flow here between u and v can't be greater 57 00:03:17,650 --> 00:03:21,020 than the capacity from u to v. 58 00:03:21,020 --> 00:03:24,350 We see that the flow is always less than 59 00:03:24,350 --> 00:03:26,690 or equal to that of the capacity. 60 00:03:26,690 --> 00:03:27,773 This is the flow. 61 00:03:28,840 --> 00:03:30,033 That's the capacity. 62 00:03:31,730 --> 00:03:34,850 The flow across an edge cannot exceed 63 00:03:34,850 --> 00:03:36,753 the capacity of the edge, 64 00:03:39,400 --> 00:03:40,730 We have another constraint, 65 00:03:40,730 --> 00:03:44,920 and that is that, excluding the source and the sink, 66 00:03:44,920 --> 00:03:48,150 that the flow into every node 67 00:03:48,150 --> 00:03:51,210 equals the flow out of that node. 68 00:03:51,210 --> 00:03:55,490 And so here we have some notation that is giving us 69 00:03:56,820 --> 00:04:00,720 the sum of all the flows into node v 70 00:04:00,720 --> 00:04:03,670 through all of these edges u, v 71 00:04:03,670 --> 00:04:07,293 for all u, v in the edge set, E is the edge set. 72 00:04:08,290 --> 00:04:13,290 And we have all of the flows out of v through edges v, w 73 00:04:14,590 --> 00:04:18,470 where all the v, w's are in the edge set. 74 00:04:18,470 --> 00:04:21,460 So the flow out of a node 75 00:04:21,460 --> 00:04:24,113 has to equal the flow into the node. 76 00:04:25,020 --> 00:04:28,863 That's the flow into the node, that's the flow out, 77 00:04:30,720 --> 00:04:33,220 and for all of them except for the source and the sink, 78 00:04:33,220 --> 00:04:34,413 they have to be equal. 79 00:04:36,340 --> 00:04:40,890 Given those constraints, what constitutes a valid flow? 80 00:04:40,890 --> 00:04:44,940 Given our example, we have this capacity, two, 81 00:04:44,940 --> 00:04:46,550 the capacity from s to x, 82 00:04:46,550 --> 00:04:48,370 and we have this capacity, one, 83 00:04:48,370 --> 00:04:51,920 which is the capacity from x to t, what's a valid flow? 84 00:04:51,920 --> 00:04:53,610 We want to come up with numbers 85 00:04:53,610 --> 00:04:55,663 that satisfy these constraints. 86 00:04:56,920 --> 00:05:01,200 And one and one is a simple example here. 87 00:05:01,200 --> 00:05:05,320 So we have the flow from s to x equals one, 88 00:05:05,320 --> 00:05:08,700 and the flow from x to t equals one. 89 00:05:08,700 --> 00:05:09,960 Let's just check to make sure 90 00:05:09,960 --> 00:05:12,180 that the constraints are satisfied. 91 00:05:12,180 --> 00:05:17,180 The flow on edge u, v, where u is s and v is x, is one. 92 00:05:20,290 --> 00:05:23,790 The capacity on that same edge is two. 93 00:05:23,790 --> 00:05:27,710 One is less than two, so we're okay there. 94 00:05:27,710 --> 00:05:31,730 For this one, the capacity is one and the flow is one, 95 00:05:31,730 --> 00:05:32,760 so they're equal, 96 00:05:32,760 --> 00:05:35,790 but that's still satisfies this constraint here. 97 00:05:35,790 --> 00:05:40,020 And notice that we have one unit of flow going into x 98 00:05:40,020 --> 00:05:42,860 and one unit of flow going out of x, 99 00:05:42,860 --> 00:05:44,780 so this constraint is satisfied. 100 00:05:44,780 --> 00:05:46,010 Of course, we only have one edge. 101 00:05:46,010 --> 00:05:47,100 If we had multiple edges, 102 00:05:47,100 --> 00:05:49,890 we'd have to sum the flows into x 103 00:05:49,890 --> 00:05:52,050 and we'd have to take all the flows out of x. 104 00:05:52,050 --> 00:05:56,020 This is a simple example, but the constraints are met, 105 00:05:56,020 --> 00:06:00,130 and so this flow of one to one 106 00:06:00,130 --> 00:06:02,210 where we have one unit flowing through our network 107 00:06:02,210 --> 00:06:03,193 is a valid flow. 108 00:06:05,440 --> 00:06:06,710 This is a trivial example. 109 00:06:06,710 --> 00:06:07,870 Flow could be zero. 110 00:06:07,870 --> 00:06:10,140 And this certainly meets all the constraints, 111 00:06:10,140 --> 00:06:12,003 but it's not very interesting. 112 00:06:13,260 --> 00:06:16,530 Now, if we allowed real-valued flows, 113 00:06:16,530 --> 00:06:19,990 like we might have for electricity or water or gas, 114 00:06:19,990 --> 00:06:22,060 this would also be a valid flow, 115 00:06:22,060 --> 00:06:24,993 because 0.5 is less than two, 116 00:06:24,993 --> 00:06:28,180 0.5 is less than or equal to one, 117 00:06:28,180 --> 00:06:32,533 and we have 0.5 going into x, 0.5 going out of x, 118 00:06:32,533 --> 00:06:37,533 0.5 leaving the source, 0.5 arriving at the sink, 119 00:06:37,720 --> 00:06:41,180 and that would also be a valid flow. 120 00:06:41,180 --> 00:06:42,860 Now, of course, this wouldn't work for trains. 121 00:06:42,860 --> 00:06:44,820 You can't have half a train. 122 00:06:44,820 --> 00:06:46,900 And all the remaining examples that we'll give 123 00:06:46,900 --> 00:06:49,580 in this video will be limited to integral solutions. 124 00:06:49,580 --> 00:06:50,730 So we're only gonna deal 125 00:06:50,730 --> 00:06:53,840 with weights and flows that have integer values. 126 00:06:53,840 --> 00:06:55,833 But they could be real-valued as well. 127 00:06:57,110 --> 00:06:59,273 So let's expand a little bit, 128 00:07:00,350 --> 00:07:03,020 take a look at a slightly bigger example. 129 00:07:03,020 --> 00:07:06,110 Here's one where the flow equals the capacity. 130 00:07:06,110 --> 00:07:09,870 So the flow here and the capacity are the same. 131 00:07:09,870 --> 00:07:14,010 And let's make sure that this satisfies the constraints. 132 00:07:14,010 --> 00:07:19,010 Notice that we have three units going into x. 133 00:07:19,650 --> 00:07:22,320 We have two here and one here into x 134 00:07:22,320 --> 00:07:24,900 and three units going out of x. 135 00:07:24,900 --> 00:07:27,350 So we're good here. 136 00:07:27,350 --> 00:07:31,610 And we have two units flowing into y 137 00:07:31,610 --> 00:07:34,420 and two units flowing out of y, 138 00:07:34,420 --> 00:07:37,230 and so this constraint is satisfied. 139 00:07:37,230 --> 00:07:39,040 Since the capacity equals the flow, 140 00:07:39,040 --> 00:07:41,220 we know we're not exceeding the capacity, 141 00:07:41,220 --> 00:07:42,530 so we're good there. 142 00:07:42,530 --> 00:07:47,530 And notice also that we have four units flowing out of s 143 00:07:47,540 --> 00:07:50,063 and four units flowing into t. 144 00:07:51,060 --> 00:07:53,840 So that's the flow out of the source 145 00:07:53,840 --> 00:07:55,750 equals the flow into the sink. 146 00:07:55,750 --> 00:08:00,223 And so this is a valid flow, all right? 147 00:08:03,040 --> 00:08:04,440 Now let's look at an example 148 00:08:04,440 --> 00:08:06,970 where we have some capacity constraints. 149 00:08:06,970 --> 00:08:09,470 So here the edges out of s 150 00:08:09,470 --> 00:08:13,173 have a combined capacity of six, three and three, 151 00:08:14,160 --> 00:08:18,400 but the edges into t, two and two, 152 00:08:18,400 --> 00:08:20,530 have a combined capacity of four. 153 00:08:20,530 --> 00:08:25,463 So clearly this network can not support a flow of six, okay? 154 00:08:28,870 --> 00:08:31,010 It can't support a flow greater than four. 155 00:08:31,010 --> 00:08:34,050 So we know whatever flow that this network might support, 156 00:08:34,050 --> 00:08:37,023 it has to be four or less. 157 00:08:37,870 --> 00:08:39,570 Here on the right, we have a solution, 158 00:08:39,570 --> 00:08:43,530 a valid flow for the network that we see here on the left. 159 00:08:43,530 --> 00:08:46,020 And again, all of our constraints are met. 160 00:08:46,020 --> 00:08:48,960 The flow out of the source equals four. 161 00:08:48,960 --> 00:08:52,460 The flow into the sink equals four. 162 00:08:52,460 --> 00:08:56,510 The flow into x equals two. 163 00:08:56,510 --> 00:08:58,800 We have one from here and one from here. 164 00:08:58,800 --> 00:09:03,800 And two out, so the flow out of x equals the flow into x. 165 00:09:03,900 --> 00:09:06,640 We have three units going into y 166 00:09:06,640 --> 00:09:09,250 and three units coming out of y. 167 00:09:09,250 --> 00:09:11,970 So all of our constraints are met, 168 00:09:11,970 --> 00:09:13,683 and so this is a valid flow. 169 00:09:17,760 --> 00:09:19,860 This too is a valid flow. 170 00:09:19,860 --> 00:09:24,120 All the same constraints are met and the flow is the same. 171 00:09:24,120 --> 00:09:28,000 It's still four, but we take slightly different routes 172 00:09:28,000 --> 00:09:30,190 and we don't use this edge in the middle. 173 00:09:30,190 --> 00:09:33,860 That's fine that we have zero flow along a given edge. 174 00:09:33,860 --> 00:09:36,960 So we have flow of four here, 175 00:09:36,960 --> 00:09:39,110 we have a flow of four here, 176 00:09:39,110 --> 00:09:41,570 we have two into x, two out of x, 177 00:09:41,570 --> 00:09:44,730 two into y, two out of y, and we're good. 178 00:09:44,730 --> 00:09:46,523 So that is a valid flow. 179 00:09:47,390 --> 00:09:50,410 And this is in fact the maximum flow 180 00:09:50,410 --> 00:09:52,653 for this particular network is four. 181 00:09:54,690 --> 00:09:57,190 Now let's take a look at a bigger example. 182 00:09:57,190 --> 00:10:00,870 Let's say we have this directed graph, okay, 183 00:10:00,870 --> 00:10:04,160 and we have these edge weights indicating the capacities, 184 00:10:04,160 --> 00:10:06,620 and we want to know what is the maximum flow 185 00:10:06,620 --> 00:10:10,993 through this network from node s over here to node t. 186 00:10:12,290 --> 00:10:14,980 Now, having seen the previous example, 187 00:10:14,980 --> 00:10:17,600 it's likely that it occurs to you 188 00:10:17,600 --> 00:10:22,450 that clearly the network can not exceed flow 189 00:10:22,450 --> 00:10:27,220 equal to the sum of the edges out of s 190 00:10:27,220 --> 00:10:30,060 or the sum of the edges into t. 191 00:10:30,060 --> 00:10:31,970 And if you thought that, you'd be right, 192 00:10:31,970 --> 00:10:33,570 that's a good intuition to have. 193 00:10:34,890 --> 00:10:39,890 So the maximum flow out of node s is 23 plus 18 is 41, 194 00:10:43,140 --> 00:10:48,140 and the maximum flow into t is 14 plus 25, that's 39. 195 00:10:48,600 --> 00:10:50,540 So we know that the maximum flow 196 00:10:50,540 --> 00:10:53,360 through the network can not exceed 39. 197 00:10:53,360 --> 00:10:56,763 It might be lower, but we know it can't exceed 39. 198 00:10:57,600 --> 00:11:00,710 And notice I've drawn these as dotted lines here. 199 00:11:02,180 --> 00:11:05,740 These are called cuts, and a cut 200 00:11:05,740 --> 00:11:09,580 is a removal of edges from a graph 201 00:11:09,580 --> 00:11:12,150 that separates components of the graph. 202 00:11:12,150 --> 00:11:15,000 And here, the components that we're interested in 203 00:11:15,000 --> 00:11:16,770 are the source and the sink. 204 00:11:16,770 --> 00:11:19,940 So if I were to make this cut and remove these two edges, 205 00:11:19,940 --> 00:11:22,070 s would be separated from t. 206 00:11:22,070 --> 00:11:25,750 There would no longer be a path from s to t. 207 00:11:25,750 --> 00:11:28,410 Or considering the cut on the right over here, 208 00:11:28,410 --> 00:11:30,883 if we were to remove these two edges, 209 00:11:31,980 --> 00:11:34,700 we would disconnect t from the rest of the network. 210 00:11:34,700 --> 00:11:37,880 And again, there would be no path from s to t. 211 00:11:37,880 --> 00:11:40,610 That's what it means to make a cut. 212 00:11:40,610 --> 00:11:43,670 We say the cut on the left has a weight of 41 213 00:11:43,670 --> 00:11:48,630 and the cut on the right has a weight of 39. 214 00:11:48,630 --> 00:11:53,300 Now, there are many, many, many other cuts in this network, 215 00:11:53,300 --> 00:11:55,600 as you might suspect. 216 00:11:55,600 --> 00:11:57,160 So we have a cut like this. 217 00:11:57,160 --> 00:12:00,090 There's this one that goes this way 218 00:12:00,090 --> 00:12:03,362 and cuts through all of these edges that it crosses. 219 00:12:03,362 --> 00:12:08,362 They have weights 18, four, six, 19, seven, four, and 16. 220 00:12:10,250 --> 00:12:13,123 So the sum of those weights is 74. 221 00:12:14,070 --> 00:12:16,550 We've got this cut, let's see, 222 00:12:16,550 --> 00:12:21,550 this cuts through nine, 10, seven, five, and 15, that's 46. 223 00:12:25,520 --> 00:12:28,960 We've got this one, this one here. 224 00:12:28,960 --> 00:12:31,240 I'm not gonna go through all of them, but you get the idea. 225 00:12:31,240 --> 00:12:36,083 This is nine, 17, six, five, and two, that's 39. 226 00:12:38,300 --> 00:12:41,670 And here we have a cut through 14, 227 00:12:41,670 --> 00:12:46,473 three, nine, 19, and two, that's 38. 228 00:12:48,000 --> 00:12:53,000 So it looks like the smallest, this one is 39, 229 00:12:54,620 --> 00:12:57,210 so it looks like the smallest cut 230 00:12:57,210 --> 00:13:02,210 that we've seen so far is 39, or 38, sorry. 231 00:13:02,420 --> 00:13:04,090 So we found a smaller cut. 232 00:13:04,090 --> 00:13:06,100 And now we know that the maximum flow 233 00:13:06,100 --> 00:13:10,340 through this network can not exceed 38. 234 00:13:10,340 --> 00:13:14,760 Because this cut separates s and t, 235 00:13:14,760 --> 00:13:19,410 we know that any flow through this network from s to t 236 00:13:19,410 --> 00:13:23,380 has to pass through at least some of the edges of this cut. 237 00:13:23,380 --> 00:13:26,810 And so if we have a weight here of 38, 238 00:13:26,810 --> 00:13:29,230 we know that there can be no greater flow 239 00:13:29,230 --> 00:13:31,430 through this network than 38. 240 00:13:31,430 --> 00:13:33,653 It's got to pass somewhere through this cut. 241 00:13:35,240 --> 00:13:39,680 It turns out that the maximum flow through the network 242 00:13:39,680 --> 00:13:41,920 and the minimum cut through the network 243 00:13:41,920 --> 00:13:44,580 are two sides of the same coin. 244 00:13:44,580 --> 00:13:46,660 So finding the minimum cut 245 00:13:46,660 --> 00:13:50,203 amounts to finding the maximum flow, and vice versa. 246 00:13:51,110 --> 00:13:52,640 So finding the minimum cut 247 00:13:52,640 --> 00:13:56,530 amounts to finding the maximum flow, and vice versa. 248 00:13:56,530 --> 00:13:59,010 Now, we want an algorithm that will find 249 00:13:59,010 --> 00:14:02,323 the maximum flow or the minimum cut through a network. 250 00:14:05,220 --> 00:14:10,220 Now, Ford-Fulkerson algorithm originated in 1956 251 00:14:10,410 --> 00:14:14,090 in a joint paper by, surprise, Ford and Fulkerson. 252 00:14:14,090 --> 00:14:15,620 And yes, that's the same Ford 253 00:14:15,620 --> 00:14:18,620 as in the Bellman-Ford algorithm. 254 00:14:18,620 --> 00:14:21,280 Edmonds-Karp is an adaptation 255 00:14:21,280 --> 00:14:25,630 of the Ford-Fulkerson algorithm that was published in 1972, 256 00:14:25,630 --> 00:14:27,440 though essentially the same algorithm 257 00:14:27,440 --> 00:14:28,960 was published independently 258 00:14:28,960 --> 00:14:33,593 by poor Yefim Dinitz in Israel in 1970. 259 00:14:34,550 --> 00:14:37,970 So unfortunately his name is not attached to the algorithm, 260 00:14:37,970 --> 00:14:40,483 and we know it by the name Edmonds-Karp. 261 00:14:41,730 --> 00:14:43,870 Karger-Stein is a later algorithm 262 00:14:43,870 --> 00:14:46,580 first published by Karger in 1993 263 00:14:46,580 --> 00:14:50,590 and then improved by Karger and Stein in 1996. 264 00:14:50,590 --> 00:14:52,320 It's a completely different algorithm 265 00:14:52,320 --> 00:14:53,780 than what we'll demonstrate here. 266 00:14:53,780 --> 00:14:56,633 So we're just gonna focus on these two. 267 00:14:57,790 --> 00:15:00,790 And Ford-Fulkerson and Edmonds-Karp 268 00:15:00,790 --> 00:15:03,620 work to find the maximum flow, 269 00:15:03,620 --> 00:15:07,650 and by doing so, they find the minimum cut. 270 00:15:07,650 --> 00:15:12,430 Karger-Stein is designed to find the minimum cut first. 271 00:15:12,430 --> 00:15:14,713 So they function very differently. 272 00:15:15,750 --> 00:15:18,600 But in case you're curious, Karger-Stein is kind of cool. 273 00:15:20,630 --> 00:15:22,620 So how do we do this? 274 00:15:22,620 --> 00:15:26,990 Well, let's start with a graph that has, 275 00:15:26,990 --> 00:15:28,330 you know, it's a directed graph. 276 00:15:28,330 --> 00:15:30,170 It's got a source and a sink 277 00:15:30,170 --> 00:15:31,820 and it's got some directed edges, 278 00:15:31,820 --> 00:15:33,670 and it's got weights on those edges 279 00:15:33,670 --> 00:15:36,670 which are the capacities, and so I've written capacity here. 280 00:15:37,960 --> 00:15:41,223 And we want to find the maximum flow through this network. 281 00:15:42,370 --> 00:15:46,970 As we saw before, clearly the flow can't exceed seven, 282 00:15:46,970 --> 00:15:50,160 because we know we have seven flowing out of s, 283 00:15:50,160 --> 00:15:52,340 we've got nine flowing into t. 284 00:15:52,340 --> 00:15:55,570 I shouldn't say that, I'm gonna take a step back. 285 00:15:55,570 --> 00:15:59,760 We have a capacity of seven out of s 286 00:15:59,760 --> 00:16:04,760 and we have a capacity of nine into t. 287 00:16:04,880 --> 00:16:09,830 So we know, because the flow cannot exceed the capacity, 288 00:16:09,830 --> 00:16:14,450 that the flow cannot exceed seven through this network. 289 00:16:14,450 --> 00:16:16,653 So we know that's a limitation right there. 290 00:16:18,430 --> 00:16:20,790 But is that the maximum flow? 291 00:16:20,790 --> 00:16:23,610 So to solve this algorithmically, 292 00:16:23,610 --> 00:16:26,340 and for purposes of demonstration, 293 00:16:26,340 --> 00:16:30,190 I'm just gonna draw two auxiliary graphs. 294 00:16:30,190 --> 00:16:33,410 And there are more concise ways of doing this, 295 00:16:33,410 --> 00:16:36,550 but this will make it easy to demonstrate. 296 00:16:36,550 --> 00:16:39,820 So we have one auxiliary graph that's the flows, 297 00:16:39,820 --> 00:16:42,160 and we initialize that auxiliary graph 298 00:16:42,160 --> 00:16:46,690 so that all the edges are initialized to zero. 299 00:16:46,690 --> 00:16:49,743 So right now we have zero flow through the graph. 300 00:16:51,240 --> 00:16:54,300 And we have what's called a residual graph, 301 00:16:54,300 --> 00:16:59,020 and we're gonna initialize that to all the same capacities 302 00:16:59,020 --> 00:17:01,480 that we have in the in the original graph. 303 00:17:01,480 --> 00:17:04,740 So we have the flow graph and the residual graph. 304 00:17:04,740 --> 00:17:07,410 And again, this is a perfectly reasonable flow. 305 00:17:07,410 --> 00:17:10,110 It's zero, but that's not very interesting. 306 00:17:10,110 --> 00:17:13,793 We want to find the maximum flow through this network. 307 00:17:14,850 --> 00:17:16,640 So the residual graph is used 308 00:17:16,640 --> 00:17:18,940 to keep track of unused capacity. 309 00:17:18,940 --> 00:17:21,380 And since the flows here are zero, 310 00:17:21,380 --> 00:17:22,970 all of our capacities are gonna 311 00:17:22,970 --> 00:17:24,283 equal the original capacities here 312 00:17:24,283 --> 00:17:27,920 because we haven't used any of them yet, all right? 313 00:17:27,920 --> 00:17:32,020 And the idea is to find paths in the residual graph 314 00:17:33,020 --> 00:17:36,983 and find the maximum flow through each path that we find, 315 00:17:38,010 --> 00:17:41,190 and add the flows to the flow graph 316 00:17:41,190 --> 00:17:44,300 and subtract the flows from the residual graph. 317 00:17:44,300 --> 00:17:47,890 And we keep doing this until we can find no more paths 318 00:17:47,890 --> 00:17:50,963 that can carry flow from the source to the sink. 319 00:17:51,890 --> 00:17:55,140 And we call these paths augmenting paths 320 00:17:55,140 --> 00:17:57,860 because once discovered, we will use them 321 00:17:57,860 --> 00:18:00,630 to augment the flow in the flow graph. 322 00:18:00,630 --> 00:18:02,303 So let's take it step by step. 323 00:18:03,350 --> 00:18:06,800 So just recall, the first thing we're gonna do 324 00:18:06,800 --> 00:18:11,720 is look for a path from s to t in this graph. 325 00:18:11,720 --> 00:18:13,130 And so we found one. 326 00:18:13,130 --> 00:18:15,840 Here's one such augmenting path. 327 00:18:15,840 --> 00:18:18,330 Now, how much flow can this path carry? 328 00:18:18,330 --> 00:18:22,900 This capacity is three, this capacity is three, this is six, 329 00:18:22,900 --> 00:18:27,170 so the maximum this path can carry is three. 330 00:18:27,170 --> 00:18:32,170 So we add three units to the flow graph, 331 00:18:33,580 --> 00:18:36,030 adding three to each one 332 00:18:36,030 --> 00:18:39,860 of the corresponding edges in the flow graph, 333 00:18:39,860 --> 00:18:42,670 and we deduct three units each 334 00:18:42,670 --> 00:18:45,740 from the edges in the residual graph. 335 00:18:45,740 --> 00:18:48,710 So now this one was three, it's now zero; 336 00:18:48,710 --> 00:18:51,680 was three, now zero; was six, now it's three. 337 00:18:51,680 --> 00:18:53,740 And we have three, three, and three over here. 338 00:18:53,740 --> 00:18:58,740 So we have this flow of three units now in our flow graph. 339 00:18:58,750 --> 00:19:00,020 Are we done yet? 340 00:19:00,020 --> 00:19:04,360 Well, can we find another augmenting path 341 00:19:04,360 --> 00:19:05,943 through the residual graph? 342 00:19:07,010 --> 00:19:10,690 So let's look, and, yep, we can find another. 343 00:19:10,690 --> 00:19:13,570 Here's another augmenting path from s to t 344 00:19:13,570 --> 00:19:15,123 that goes through b and c. 345 00:19:16,010 --> 00:19:18,630 And what's the maximum flow this path can carry? 346 00:19:18,630 --> 00:19:20,980 Well, the capacity here is four, 347 00:19:20,980 --> 00:19:23,030 the capacity here is one, 348 00:19:23,030 --> 00:19:25,230 and this is the leftover capacity 349 00:19:25,230 --> 00:19:27,460 after consuming three over here. 350 00:19:27,460 --> 00:19:31,810 So we have three remaining units of capacity here. 351 00:19:31,810 --> 00:19:34,970 But the bottleneck is in this edge from b to c. 352 00:19:34,970 --> 00:19:39,680 This edge can only carry one unit of flow. 353 00:19:39,680 --> 00:19:41,980 And so what we're gonna do 354 00:19:41,980 --> 00:19:44,730 is we're gonna add one unit of flow 355 00:19:44,730 --> 00:19:48,220 to the corresponding edges in the flow graph 356 00:19:48,220 --> 00:19:52,190 and we're going to deduct those units 357 00:19:52,190 --> 00:19:53,840 from the residual graph, 358 00:19:53,840 --> 00:19:56,150 from the edges in the residual graph, right? 359 00:19:56,150 --> 00:19:58,100 So this was four, now it's three; 360 00:19:58,100 --> 00:19:59,490 this was one, now it's zero; 361 00:19:59,490 --> 00:20:01,240 this was three, now it's two. 362 00:20:01,240 --> 00:20:03,980 And we have one, one, and four. 363 00:20:03,980 --> 00:20:06,680 This had been three before, we added one. 364 00:20:06,680 --> 00:20:11,680 And so now we have a flow of four through our network. 365 00:20:11,860 --> 00:20:13,070 Are we done? 366 00:20:13,070 --> 00:20:14,910 Nope, we're not done. 367 00:20:14,910 --> 00:20:16,450 So we've gotta go back and we've gotta see 368 00:20:16,450 --> 00:20:19,003 if we can find another augmenting path. 369 00:20:20,110 --> 00:20:22,370 And yep, there's another one. 370 00:20:22,370 --> 00:20:24,650 So what's the maximum flow for this path? 371 00:20:24,650 --> 00:20:28,570 It's two, 'cause we have capacity three, two, and three. 372 00:20:28,570 --> 00:20:31,583 So the most we can flow through this path is two. 373 00:20:33,250 --> 00:20:38,250 So we add two to the corresponding edges in our flow graph 374 00:20:40,750 --> 00:20:45,750 and we deduct two from the edges in our residual graph. 375 00:20:47,100 --> 00:20:50,660 And so now what do we have? 376 00:20:50,660 --> 00:20:53,770 Now we hunt for another augmenting path. 377 00:20:53,770 --> 00:20:56,400 Is there another augmenting path? 378 00:20:56,400 --> 00:20:57,270 No, there's not. 379 00:20:57,270 --> 00:21:01,580 There's no way we can get through the residual graph, now, 380 00:21:01,580 --> 00:21:05,440 from s to t along any path 381 00:21:05,440 --> 00:21:07,300 that has a capacity greater than zero. 382 00:21:07,300 --> 00:21:10,440 This is zero, this is zero, this is zero, this is zero. 383 00:21:10,440 --> 00:21:13,390 So all of our routes are blocked. 384 00:21:13,390 --> 00:21:17,570 We can't find any more augmenting paths. 385 00:21:17,570 --> 00:21:22,510 And since we can find no more augmenting paths, we're done. 386 00:21:22,510 --> 00:21:24,110 And on the left, we have, again, 387 00:21:24,110 --> 00:21:27,740 our original graph showing the capacities of each edge. 388 00:21:27,740 --> 00:21:30,080 In the middle, we have a graph indicating 389 00:21:30,080 --> 00:21:32,303 a maximum flow through the network. 390 00:21:33,440 --> 00:21:34,820 This is a solution, 391 00:21:34,820 --> 00:21:39,130 not necessarily the only solution, it's a solution. 392 00:21:39,130 --> 00:21:42,990 And when our algorithm has terminated, 393 00:21:42,990 --> 00:21:46,950 the residual graph shows the remaining unused capacities, 394 00:21:46,950 --> 00:21:50,568 and it also gives us a hint as to the minimum cut here. 395 00:21:50,568 --> 00:21:52,500 You have these three zeros. 396 00:21:52,500 --> 00:21:53,820 Let's just double-check. 397 00:21:53,820 --> 00:21:56,490 Are all of our constraints met? 398 00:21:56,490 --> 00:22:00,830 And we just do an edgewise comparison and make sure. 399 00:22:00,830 --> 00:22:03,980 Three is less than or equal to three, 400 00:22:03,980 --> 00:22:05,710 three is less than or equal to four, 401 00:22:05,710 --> 00:22:07,540 zero is less than or equal to two, 402 00:22:07,540 --> 00:22:10,640 you can do the rest of them, but trust me, 403 00:22:10,640 --> 00:22:12,800 all of these values in the flow graph 404 00:22:12,800 --> 00:22:14,690 are less than or equal to the values 405 00:22:14,690 --> 00:22:17,160 of the corresponding edges in the capacity graph. 406 00:22:17,160 --> 00:22:21,033 So this one is satisfied, this constraint is satisfied. 407 00:22:22,490 --> 00:22:25,660 Is the flow excluding the source and the sink? 408 00:22:25,660 --> 00:22:28,610 Is the flow into each node 409 00:22:28,610 --> 00:22:30,640 equal to the flow out of each node? 410 00:22:30,640 --> 00:22:32,700 And here we have three going into a 411 00:22:32,700 --> 00:22:35,600 and three going out of a, so we're good at a. 412 00:22:35,600 --> 00:22:37,300 We have three going into b 413 00:22:37,300 --> 00:22:40,060 and one plus two is three going out of b, 414 00:22:40,060 --> 00:22:41,640 so we're good there. 415 00:22:41,640 --> 00:22:45,530 We have four going into c and four going out of c, 416 00:22:45,530 --> 00:22:46,990 so we're good there. 417 00:22:46,990 --> 00:22:50,240 And we have two going into d and two coming out of d, 418 00:22:50,240 --> 00:22:51,820 so we're good there. 419 00:22:51,820 --> 00:22:56,820 And, final check, is the flow out of the source 420 00:22:57,580 --> 00:23:00,260 equal to the flow into the sink? 421 00:23:00,260 --> 00:23:02,390 And here we have three plus three is six, 422 00:23:02,390 --> 00:23:03,940 four plus two is six. 423 00:23:03,940 --> 00:23:08,090 So all of our constraints are met and this is a valid flow. 424 00:23:08,090 --> 00:23:10,763 So we found a solution and we verified. 425 00:23:12,560 --> 00:23:14,860 So all of our constraints are met. 426 00:23:14,860 --> 00:23:17,070 The flow along each edge is less than 427 00:23:17,070 --> 00:23:19,040 or equal to that of the edge's capacity. 428 00:23:19,040 --> 00:23:20,440 Apart from the source and the sink, 429 00:23:20,440 --> 00:23:23,593 all the flows into a node equal the flows out. 430 00:23:25,610 --> 00:23:28,593 And we're good, it's a valid flow. 431 00:23:29,955 --> 00:23:33,190 And we can also see that the maximum flow, which is six, 432 00:23:33,190 --> 00:23:35,420 equals the weight of the minimum cut, six. 433 00:23:35,420 --> 00:23:38,070 And here's the minimum cut through this graph. 434 00:23:38,070 --> 00:23:41,050 See, it cuts through an edge three, one, and two. 435 00:23:41,050 --> 00:23:42,610 Those sum to six. 436 00:23:42,610 --> 00:23:47,150 It should come as no surprise that that cut 437 00:23:47,150 --> 00:23:51,970 goes through values of zero here in the residual graph. 438 00:23:51,970 --> 00:23:54,040 And so here's our minimum cut. 439 00:23:54,040 --> 00:23:56,090 Here's our maximum flow. 440 00:23:56,090 --> 00:23:57,650 And like I said before, 441 00:23:57,650 --> 00:23:59,450 they are two sides of the same coin. 442 00:24:01,990 --> 00:24:04,173 So is this a greedy algorithm? 443 00:24:05,210 --> 00:24:06,560 Yep, sure is. 444 00:24:06,560 --> 00:24:08,610 This is a greedy algorithm. 445 00:24:08,610 --> 00:24:10,590 This algorithm adds flows 446 00:24:10,590 --> 00:24:12,710 to the solution as they're discovered 447 00:24:12,710 --> 00:24:15,840 and never removes a flow once it's been added. 448 00:24:15,840 --> 00:24:17,414 Okay, when we went through all those steps, 449 00:24:17,414 --> 00:24:21,363 we never deducted anything from our flows. 450 00:24:22,740 --> 00:24:24,700 What's the complexity? 451 00:24:24,700 --> 00:24:29,700 Well, assuming we have only integer weights and flows, 452 00:24:30,600 --> 00:24:33,240 like I said, the complexity is big O 453 00:24:33,240 --> 00:24:37,760 of the cardinality of the edge set times the flow. 454 00:24:37,760 --> 00:24:39,423 Well, why times the flow? 455 00:24:40,490 --> 00:24:44,560 Well, in the worst case, we'll augment the flow by one 456 00:24:44,560 --> 00:24:47,203 for each augmenting path that we find. 457 00:24:49,050 --> 00:24:51,480 But we can only do this f times 458 00:24:51,480 --> 00:24:54,080 if the maximum flow is a f units. 459 00:24:54,080 --> 00:24:56,910 So in the worst case, every edge could be part 460 00:24:56,910 --> 00:24:59,740 of each augmenting path we find, 461 00:24:59,740 --> 00:25:02,220 and so we get a worst case of big O 462 00:25:02,220 --> 00:25:04,963 of the cardinality of the edge set times the flow. 463 00:25:07,870 --> 00:25:11,080 Now, how do we find the augmenting paths? 464 00:25:11,080 --> 00:25:14,270 We looked at a small example and we found three, 465 00:25:14,270 --> 00:25:16,973 and then we found there were no more. 466 00:25:18,070 --> 00:25:20,480 But the answer here is it depends. 467 00:25:20,480 --> 00:25:25,100 And Ford-Fulkerson does not precisely specify this. 468 00:25:25,100 --> 00:25:25,933 As a matter of fact, 469 00:25:25,933 --> 00:25:28,730 some people call it the Ford-Fulkerson method 470 00:25:28,730 --> 00:25:29,890 because they don't believe 471 00:25:29,890 --> 00:25:34,240 that it quite achieves the title of algorithm. 472 00:25:34,240 --> 00:25:35,893 I think that's a little nitpicky. 473 00:25:36,820 --> 00:25:40,320 But the Edmonds-Karp algorithm does specify 474 00:25:40,320 --> 00:25:42,923 how we find the augmenting paths. 475 00:25:43,760 --> 00:25:46,230 So at least in the case of Ford-Fulkerson, 476 00:25:46,230 --> 00:25:48,670 what we've seen here is a certain arbitrariness 477 00:25:48,670 --> 00:25:52,143 regarding the order in which we find the augmenting paths. 478 00:25:53,110 --> 00:25:54,280 And depending on the graph, 479 00:25:54,280 --> 00:25:55,810 a different order of discovery 480 00:25:55,810 --> 00:25:57,430 may yield different solutions. 481 00:25:57,430 --> 00:25:59,460 The solutions will all be the same, 482 00:25:59,460 --> 00:26:02,590 they'll still yield the same maximum flow, 483 00:26:02,590 --> 00:26:06,000 but the flow may occur differently 484 00:26:06,000 --> 00:26:08,690 through all the different edges in the network. 485 00:26:08,690 --> 00:26:10,550 So again, this algorithm doesn't find 486 00:26:10,550 --> 00:26:12,570 all the possible maximum flows, 487 00:26:12,570 --> 00:26:15,970 it finds a maximum flow. 488 00:26:15,970 --> 00:26:17,600 And so that's all for this video 489 00:26:17,600 --> 00:26:21,570 and we will continue in a subsequent video. 490 00:26:21,570 --> 00:26:22,603 Thanks, bye.