1 00:00:01,160 --> 00:00:02,920 - [Instructor] Okay, now we're gonna continue 2 00:00:02,920 --> 00:00:06,683 our presentation of the Ford-Fulkerson algorithm. 3 00:00:07,930 --> 00:00:10,810 And just to recap a little, 4 00:00:10,810 --> 00:00:12,700 in an earlier video we presented 5 00:00:12,700 --> 00:00:14,850 the idea of flow in a network 6 00:00:14,850 --> 00:00:16,863 and we gave a number of examples. 7 00:00:17,950 --> 00:00:22,950 And we saw how to represent flows with a graph 8 00:00:22,960 --> 00:00:25,890 and how to calculate the maximum flow 9 00:00:25,890 --> 00:00:30,890 by iteratively finding augmenting paths in a residual graph. 10 00:00:31,510 --> 00:00:35,510 So here we have the example that we worked out 11 00:00:35,510 --> 00:00:36,470 in the last video, 12 00:00:36,470 --> 00:00:41,150 we have the capacity graph with all of the C sub u, v. 13 00:00:41,150 --> 00:00:45,280 We have the flows, these are all the F sub u, v, 14 00:00:45,280 --> 00:00:47,530 and then we have the residual graph 15 00:00:47,530 --> 00:00:50,870 which is the remaining capacity 16 00:00:50,870 --> 00:00:55,870 after we've found augmenting paths and updated our flows. 17 00:00:57,610 --> 00:01:00,430 So again, we calculate the maximum flow 18 00:01:00,430 --> 00:01:03,313 by iteratively finding augmenting paths. 19 00:01:04,300 --> 00:01:06,480 And to continue to recap, 20 00:01:06,480 --> 00:01:10,023 we also saw that flows are subject to certain constraints. 21 00:01:11,560 --> 00:01:14,480 For example, that the flow along an edge 22 00:01:14,480 --> 00:01:16,920 can't exceed the edges capacity. 23 00:01:16,920 --> 00:01:18,840 That's common sense. 24 00:01:18,840 --> 00:01:23,040 Also common sense that apart from the source and the sink, 25 00:01:23,040 --> 00:01:26,280 the flow into any given node must equal 26 00:01:26,280 --> 00:01:28,843 the flow out of the node, okay? 27 00:01:30,350 --> 00:01:34,010 And last we saw that the flow out of the source, 28 00:01:34,010 --> 00:01:38,940 this is the source here s and the flow into the sink 29 00:01:38,940 --> 00:01:42,380 these are all the edges w, t, the flow into the sink, 30 00:01:42,380 --> 00:01:47,380 these are all of the edges s, u that flow out of the source, 31 00:01:47,750 --> 00:01:49,740 their sums have to be the same. 32 00:01:49,740 --> 00:01:51,460 So the flow out of the source 33 00:01:51,460 --> 00:01:53,433 has to equal the flow into the sink. 34 00:01:55,090 --> 00:01:58,720 I'm guilty, I'm guilty. 35 00:01:58,720 --> 00:02:00,020 In the previous video, 36 00:02:00,020 --> 00:02:03,410 I swept an important detail under the rug. 37 00:02:03,410 --> 00:02:08,410 And in this video, we'll demonstrate the problem here 38 00:02:08,957 --> 00:02:10,703 with this small example. 39 00:02:11,790 --> 00:02:15,590 And as before, we have the capacity network 40 00:02:15,590 --> 00:02:16,930 here on the left, 41 00:02:16,930 --> 00:02:19,770 and all the edges labeled with all the capacities 42 00:02:19,770 --> 00:02:21,430 the C sub u, v, 43 00:02:21,430 --> 00:02:24,360 and here we have the initial state of our flow network. 44 00:02:24,360 --> 00:02:25,840 Everything's initialized to zero. 45 00:02:25,840 --> 00:02:27,603 These are all of the F sub u, v. 46 00:02:28,580 --> 00:02:32,800 And here we have the residual network, which we initialize 47 00:02:32,800 --> 00:02:37,090 to the capacities and the flows are zero. 48 00:02:37,090 --> 00:02:40,140 So, C sub u, v minus F sub u, v 49 00:02:40,140 --> 00:02:42,270 is going to be C sub u, v 50 00:02:42,270 --> 00:02:45,463 because F sub u, v is zero in the initial condition. 51 00:02:46,780 --> 00:02:49,560 So this is our starting point. 52 00:02:49,560 --> 00:02:52,830 And let's just examine this problem for a second here. 53 00:02:52,830 --> 00:02:55,630 Let's go back over here to this capacity graph. 54 00:02:55,630 --> 00:03:00,630 And we can see just by looking at this small example 55 00:03:01,360 --> 00:03:05,350 that the maximum flow that this capacity network here 56 00:03:05,350 --> 00:03:07,370 can support is five. 57 00:03:07,370 --> 00:03:08,543 We can see that. 58 00:03:08,543 --> 00:03:09,940 It should be playing. 59 00:03:09,940 --> 00:03:14,890 So we should have three units of flow along this edge, 60 00:03:14,890 --> 00:03:18,840 one unit of flow along this edge, three units 61 00:03:18,840 --> 00:03:22,920 of flow along this edge, two units of flow along this edge 62 00:03:22,920 --> 00:03:25,860 and two units of flow along this edge. 63 00:03:25,860 --> 00:03:30,860 So that's gonna give us a total maximum flow of five 64 00:03:31,070 --> 00:03:33,500 but let me show you how we can go wrong 65 00:03:33,500 --> 00:03:35,790 with this very, very small problem instance. 66 00:03:35,790 --> 00:03:39,880 And it all hinges on the fact that with Ford-Fulkerson, 67 00:03:39,880 --> 00:03:44,773 we don't specify how we discover our augmenting paths. 68 00:03:45,650 --> 00:03:50,500 And so what if we discover this augmenting path here first? 69 00:03:50,500 --> 00:03:53,690 It's perfectly reasonable that's a fine augmenting path. 70 00:03:53,690 --> 00:03:56,870 We have a bottleneck of three here. 71 00:03:56,870 --> 00:04:01,870 So this augmenting path can support a flow of three. 72 00:04:02,310 --> 00:04:04,400 And so we're gonna update our flow. 73 00:04:04,400 --> 00:04:06,400 So we have three, three, and three 74 00:04:06,400 --> 00:04:09,740 and we're going to deduct three from here, 75 00:04:09,740 --> 00:04:12,190 three from here and three from here. 76 00:04:12,190 --> 00:04:13,690 But now we have a problem. 77 00:04:13,690 --> 00:04:15,300 Look at the residual graph. 78 00:04:15,300 --> 00:04:16,443 What's the problem? 79 00:04:18,360 --> 00:04:22,901 The problem is that there are no more augmenting paths. 80 00:04:22,901 --> 00:04:25,870 This has zero remaining capacity 81 00:04:25,870 --> 00:04:30,030 so we can't even consider this route as an option. 82 00:04:30,030 --> 00:04:33,860 This is the only other edge out of s 83 00:04:33,860 --> 00:04:35,820 that has any remaining capacity, 84 00:04:35,820 --> 00:04:40,720 it flows to b, but then from b to t, the capacity is zero 85 00:04:40,720 --> 00:04:44,420 and there's no way to get over to a here. 86 00:04:44,420 --> 00:04:46,970 This is a directed edge so we can't go backwards 87 00:04:46,970 --> 00:04:50,790 along this edge to use this unused capacity here. 88 00:04:50,790 --> 00:04:54,640 So this is what's called a blocking flow. 89 00:04:54,640 --> 00:04:57,310 We've painted ourselves into a corner 90 00:04:57,310 --> 00:05:01,130 by a bad choice of our augmenting paths 91 00:05:01,130 --> 00:05:03,850 and we've arrived at an incorrect value 92 00:05:03,850 --> 00:05:07,250 for the max flow because the algorithm would terminate here. 93 00:05:07,250 --> 00:05:09,630 It sees that there are no more augmenting paths, 94 00:05:09,630 --> 00:05:11,440 it would say, "Okay, I'm done." 95 00:05:11,440 --> 00:05:15,280 And we'd wind up with a flow of three, three 96 00:05:15,280 --> 00:05:18,800 out of the source, three into the sink and that's wrong. 97 00:05:18,800 --> 00:05:20,690 That's just a wrong answer. 98 00:05:20,690 --> 00:05:24,520 And I swept this detail under the rug in the previous video. 99 00:05:24,520 --> 00:05:28,980 So just to prove that this does work correctly 100 00:05:28,980 --> 00:05:31,030 if we have the correct, 101 00:05:31,030 --> 00:05:34,170 a correct sequence of augmenting paths. 102 00:05:34,170 --> 00:05:35,960 Let's just walk through it real quick. 103 00:05:35,960 --> 00:05:38,540 We have three and two, we discover this one here. 104 00:05:38,540 --> 00:05:43,540 So, we're going to have a flow of two along these two edges. 105 00:05:43,620 --> 00:05:46,650 So we got two here, we deduct two from this edge 106 00:05:46,650 --> 00:05:48,680 and deduct two from this edge, 107 00:05:48,680 --> 00:05:51,390 and so now we have these remaining capacities 108 00:05:52,250 --> 00:05:56,370 and then let's say the next augmenting path 109 00:05:56,370 --> 00:06:00,900 that we find, from source to sink is this path here, 110 00:06:00,900 --> 00:06:02,990 and so this has two, this has three 111 00:06:02,990 --> 00:06:04,790 so this can support a flow of two 112 00:06:04,790 --> 00:06:07,170 so we're gonna add two here and two here 113 00:06:07,170 --> 00:06:10,020 and deduct two here and deduct two here 114 00:06:10,020 --> 00:06:11,580 and we're gonna get this, 115 00:06:11,580 --> 00:06:14,740 and then we see we have this one more augmenting path 116 00:06:15,880 --> 00:06:20,880 which can support a flow of one along this one here. 117 00:06:21,840 --> 00:06:26,000 And so we're going to update our flow and residual networks. 118 00:06:26,000 --> 00:06:28,700 And now we found the correct maximum flow. 119 00:06:28,700 --> 00:06:30,830 So there is a way to find it, 120 00:06:30,830 --> 00:06:32,540 but we're not guaranteed to find it 121 00:06:32,540 --> 00:06:36,310 because again Ford-Fulkerson doesn't specify how we go 122 00:06:36,310 --> 00:06:38,910 and find these augmenting paths. 123 00:06:38,910 --> 00:06:40,610 It just says, go out and find one. 124 00:06:41,550 --> 00:06:42,990 That's a problem. 125 00:06:42,990 --> 00:06:46,150 And so we need to modify the approach that we saw 126 00:06:46,150 --> 00:06:47,470 in the previous video 127 00:06:47,470 --> 00:06:50,430 so that we don't get stuck without recourse 128 00:06:50,430 --> 00:06:52,640 when we discover an augmenting path 129 00:06:52,640 --> 00:06:54,740 that yields a blocking flow. 130 00:06:54,740 --> 00:06:56,240 Okay, so what are we gonna do? 131 00:06:58,210 --> 00:07:00,700 The problem is by a bad sequence 132 00:07:00,700 --> 00:07:03,590 of discoveries of augmenting paths, 133 00:07:03,590 --> 00:07:05,670 we might discover a blocking flow 134 00:07:05,670 --> 00:07:09,200 which prevents us from discovering other augmenting paths. 135 00:07:09,200 --> 00:07:10,810 That's the problem. 136 00:07:10,810 --> 00:07:14,240 The solution is that we're going to encode a way 137 00:07:14,240 --> 00:07:18,390 of revising our flows in the residual graph. 138 00:07:18,390 --> 00:07:21,810 And we're gonna do that by adding backward edges. 139 00:07:21,810 --> 00:07:26,810 So where we have every single edge in the capacity graph, 140 00:07:27,000 --> 00:07:31,220 we're going to have two edges in the residual graph. 141 00:07:31,220 --> 00:07:35,790 One forward representing the unused capacity 142 00:07:35,790 --> 00:07:38,010 and one backwards representing the flow 143 00:07:38,010 --> 00:07:39,450 that we've already allocated 144 00:07:39,450 --> 00:07:42,050 in addition to the forward edges. 145 00:07:42,050 --> 00:07:45,810 And so in that way, we're going to encode a way 146 00:07:45,810 --> 00:07:49,587 of revising our flows in the event 147 00:07:49,587 --> 00:07:53,463 that otherwise would be a blocking flow. 148 00:07:54,300 --> 00:07:56,520 So we're gonna use the example 149 00:07:56,520 --> 00:07:59,700 that we gave in the previous video. 150 00:07:59,700 --> 00:08:01,160 And in the previous video, 151 00:08:01,160 --> 00:08:05,180 I showed you a sequence of discoveries 152 00:08:05,180 --> 00:08:08,450 of augmenting paths that gave us the correct solution. 153 00:08:08,450 --> 00:08:13,200 So remember that the correct solution is that the flow, 154 00:08:13,200 --> 00:08:18,200 the maximum flow in this network is six, okay? 155 00:08:18,230 --> 00:08:23,230 And we gave a good sequence of augmenting paths 156 00:08:23,800 --> 00:08:25,170 in the previous video. 157 00:08:25,170 --> 00:08:28,800 Now I'm gonna show you before I give you the solution, 158 00:08:28,800 --> 00:08:30,730 now I'm gonna show you how we can get stuck 159 00:08:30,730 --> 00:08:33,240 with this exact same example. 160 00:08:33,240 --> 00:08:37,513 So here is our series of unfortunate events. 161 00:08:38,740 --> 00:08:39,710 We're gonna start here. 162 00:08:39,710 --> 00:08:41,980 We're gonna look for augmenting paths 163 00:08:41,980 --> 00:08:44,550 in this residual network here. 164 00:08:44,550 --> 00:08:49,550 And let's say we find this one first, this one here okay? 165 00:08:49,620 --> 00:08:52,460 And you can see the bottleneck here is two, 166 00:08:52,460 --> 00:08:54,380 so this can support a flow of two, 167 00:08:54,380 --> 00:08:57,450 so we're gonna deduct two from each of these. 168 00:08:57,450 --> 00:09:01,380 We're gonna add two here, here, here, and here 169 00:09:01,380 --> 00:09:04,960 and we're gonna wind up with something that looks like this. 170 00:09:04,960 --> 00:09:07,050 So we've added a flow of two. 171 00:09:07,050 --> 00:09:09,040 Now you can see there's a flow of two 172 00:09:09,040 --> 00:09:12,700 out of the source and a flow of two into the sink. 173 00:09:12,700 --> 00:09:16,010 And we still have some remaining capacity here. 174 00:09:16,010 --> 00:09:18,960 So we're gonna go find another augmenting path 175 00:09:18,960 --> 00:09:21,300 and let's say this is the second augmenting path 176 00:09:21,300 --> 00:09:22,790 that we find. 177 00:09:22,790 --> 00:09:25,280 And the bottleneck here is this edge 178 00:09:25,280 --> 00:09:28,430 with a capacity of one, remaining capacity of one 179 00:09:28,430 --> 00:09:29,720 was the original capacity 180 00:09:29,720 --> 00:09:31,360 but it's the remaining capacity here 181 00:09:31,360 --> 00:09:33,420 in our residual network. 182 00:09:33,420 --> 00:09:36,600 And so this augmenting path can support a flow of one. 183 00:09:36,600 --> 00:09:39,460 So we're gonna add one here, one here, one here 184 00:09:39,460 --> 00:09:42,500 and we're gonna deduct one from each of these edges. 185 00:09:42,500 --> 00:09:45,890 So we're gonna wind up with something that looks like this. 186 00:09:45,890 --> 00:09:47,860 And so now we have a flow of three. 187 00:09:47,860 --> 00:09:50,820 We've got three out of the source and three into the sink. 188 00:09:50,820 --> 00:09:52,550 And we know there should be three more 189 00:09:52,550 --> 00:09:55,970 that we should be able to discover, all right? 190 00:09:55,970 --> 00:10:00,970 So let's say this is the third augmenting path we find. 191 00:10:01,740 --> 00:10:03,500 Now this has a bottleneck of one, 192 00:10:03,500 --> 00:10:06,170 so this augmenting path can support a flow of one, 193 00:10:06,170 --> 00:10:08,440 so we're gonna add one, one, one here. 194 00:10:08,440 --> 00:10:11,300 We're gonna deduct one, one, one here 195 00:10:11,300 --> 00:10:14,440 and we're gonna wind up with something like this. 196 00:10:14,440 --> 00:10:17,930 And now take a look at the residual graph. 197 00:10:17,930 --> 00:10:20,070 We are stuck, okay? 198 00:10:20,070 --> 00:10:22,770 So this is exactly the same problem that I showed you 199 00:10:22,770 --> 00:10:25,350 in the previous video, where we did find a solution. 200 00:10:25,350 --> 00:10:29,910 Here we found a sequence of augmenting paths 201 00:10:29,910 --> 00:10:32,810 that gets us stuck let's look. 202 00:10:32,810 --> 00:10:34,590 We've got a zero along this edge 203 00:10:34,590 --> 00:10:39,590 so we can't use any path that goes through a here. 204 00:10:39,810 --> 00:10:42,780 We've got three here, but if we get to b, 205 00:10:42,780 --> 00:10:44,460 we have these two zeros here, 206 00:10:44,460 --> 00:10:45,820 there's no way to flow, 207 00:10:45,820 --> 00:10:49,160 say to c or to d in order to get to t. 208 00:10:49,160 --> 00:10:51,690 We've got this unused capacity here 209 00:10:51,690 --> 00:10:53,760 but there's no way to use it. 210 00:10:53,760 --> 00:10:57,070 So there are no more augmenting paths 211 00:10:57,070 --> 00:10:59,170 in this residual network. 212 00:10:59,170 --> 00:11:00,540 And we are stuck. 213 00:11:00,540 --> 00:11:02,610 We really do have a problem. 214 00:11:02,610 --> 00:11:04,163 So how do we fix it? 215 00:11:05,670 --> 00:11:08,960 Well, like I said, for every edge 216 00:11:08,960 --> 00:11:12,470 in the original capacity network, 217 00:11:12,470 --> 00:11:17,470 we're gonna have two edges in our residual network. 218 00:11:17,660 --> 00:11:20,150 And we're gonna have these forward edges 219 00:11:20,150 --> 00:11:23,770 that match the direction of the edges 220 00:11:23,770 --> 00:11:26,230 in our capacity network, 221 00:11:26,230 --> 00:11:27,730 and we're gonna initialize them 222 00:11:27,730 --> 00:11:30,180 with the capacity just as we did before. 223 00:11:30,180 --> 00:11:32,250 But we're also gonna add for each one 224 00:11:32,250 --> 00:11:34,273 we're gonna add a backward edge, 225 00:11:35,120 --> 00:11:38,020 and we're gonna initialize all of those to zero. 226 00:11:38,020 --> 00:11:39,330 Those are the flows here. 227 00:11:39,330 --> 00:11:40,760 These are all zeros. 228 00:11:40,760 --> 00:11:43,860 These are all zeros, okay? 229 00:11:43,860 --> 00:11:47,640 So for every edge over here, we've got two here, one 230 00:11:47,640 --> 00:11:52,263 with the original capacity and one starting at zero, okay? 231 00:11:53,710 --> 00:11:56,350 This is a way of encoding flow 232 00:11:56,350 --> 00:12:00,700 so that we can undo as we run our algorithm. 233 00:12:00,700 --> 00:12:02,850 And that's how we're going to address the problem 234 00:12:02,850 --> 00:12:04,620 of blocking flows. 235 00:12:04,620 --> 00:12:08,220 Traveling backward along one of these edges amounts 236 00:12:08,220 --> 00:12:12,510 to reducing the flow that we'd previously allocated. 237 00:12:12,510 --> 00:12:14,220 Now, we're gonna start as before, 238 00:12:14,220 --> 00:12:17,880 and we're gonna discover the same sequence 239 00:12:17,880 --> 00:12:20,180 of augmenting paths that we did earlier 240 00:12:20,180 --> 00:12:22,800 that got us into a problem. 241 00:12:22,800 --> 00:12:26,180 And we'll see how using this approach here, 242 00:12:26,180 --> 00:12:27,533 gets us out of the problem. 243 00:12:28,480 --> 00:12:31,130 So we found the same augmenting path. 244 00:12:31,130 --> 00:12:32,770 This is the first one that I just showed you 245 00:12:32,770 --> 00:12:36,900 in the previous example. 246 00:12:36,900 --> 00:12:39,410 This is exactly the same augmenting flow 247 00:12:39,410 --> 00:12:41,410 or augmenting path forgive me. 248 00:12:41,410 --> 00:12:44,860 And we see again that it has a bottleneck of two. 249 00:12:44,860 --> 00:12:48,520 So we're gonna update two, two, two, two here. 250 00:12:48,520 --> 00:12:52,290 We're gonna deduct two, two, two, two here 251 00:12:52,290 --> 00:12:56,690 but we're also gonna add two to this backwards edge. 252 00:12:56,690 --> 00:12:59,580 We're gonna add two to this backwards edge. 253 00:12:59,580 --> 00:13:01,977 We're gonna add two to this backwards edge, 254 00:13:01,977 --> 00:13:04,510 and we're gonna add two to this backwards edge 255 00:13:04,510 --> 00:13:07,510 that represents the flow that we're adding here 256 00:13:07,510 --> 00:13:12,093 and flow that we might decide we wanna reallocate later. 257 00:13:13,300 --> 00:13:15,800 So we're gonna wind up with something that looks like this. 258 00:13:15,800 --> 00:13:19,790 See, two, two, two, two, and this has been reduced to one 259 00:13:19,790 --> 00:13:22,310 and then all of these that were at zero 260 00:13:22,310 --> 00:13:24,203 are now at two, okay? 261 00:13:25,180 --> 00:13:28,040 So we have those two updates to the residual network. 262 00:13:28,040 --> 00:13:31,030 We deduct the new flow from the forward edges as before, 263 00:13:31,030 --> 00:13:33,300 so that's the new available capacity, 264 00:13:33,300 --> 00:13:36,550 and we add the flow to the corresponding backward edges 265 00:13:36,550 --> 00:13:38,260 these dotted edges here, 266 00:13:38,260 --> 00:13:41,980 and that represents the flow that we can undo if we need to. 267 00:13:41,980 --> 00:13:44,660 So now we do the same thing. 268 00:13:44,660 --> 00:13:47,050 We go and we hunt for another augmenting path 269 00:13:47,050 --> 00:13:49,070 and we're gonna find the same one that we found 270 00:13:49,070 --> 00:13:50,320 in the previous example. 271 00:13:50,320 --> 00:13:53,563 This is the second path that we found this one here. 272 00:13:54,404 --> 00:13:55,993 This has a capacity of one. 273 00:13:58,850 --> 00:14:00,940 It can support a flow of one. 274 00:14:00,940 --> 00:14:04,370 And so we're gonna add one, one, one here. 275 00:14:04,370 --> 00:14:06,710 We're gonna deduct one, one, one here, 276 00:14:06,710 --> 00:14:09,930 and we're gonna add one to this backward edge, add one 277 00:14:09,930 --> 00:14:13,003 to this backward edge and add one to this backward edge. 278 00:14:15,430 --> 00:14:19,280 Now, again, we're gonna hunt for an augmenting path 279 00:14:19,280 --> 00:14:21,870 and we'll find the third path that we found 280 00:14:21,870 --> 00:14:25,120 in the previous example exactly the same sequence. 281 00:14:25,120 --> 00:14:30,120 This one again supports a flow of one. 282 00:14:30,840 --> 00:14:33,120 The bottleneck here is this edge. 283 00:14:33,120 --> 00:14:37,060 And so we're gonna add one, one, one to this flow 284 00:14:37,060 --> 00:14:40,470 and we're going to deduct one to get zero, 285 00:14:40,470 --> 00:14:43,610 one to get two, one to get four and we're gonna add one 286 00:14:43,610 --> 00:14:47,053 to each one of these backward edges, okay? 287 00:14:48,010 --> 00:14:50,440 And so we're gonna wind up with something 288 00:14:50,440 --> 00:14:51,273 that looks like this. 289 00:14:51,273 --> 00:14:55,210 Now this is the place where we got stuck the last time. 290 00:14:55,210 --> 00:14:56,993 This is where we got stuck. 291 00:14:58,170 --> 00:15:01,350 But now if we consider all the edges 292 00:15:01,350 --> 00:15:04,793 in our residual network, including these backward edges, 293 00:15:05,640 --> 00:15:08,700 we can find an augmenting path 294 00:15:08,700 --> 00:15:11,350 through this residual network. 295 00:15:11,350 --> 00:15:12,823 And that's this one here, 296 00:15:14,250 --> 00:15:18,420 and notice now that we're using one of these backward edges, 297 00:15:18,420 --> 00:15:22,263 and we're gonna wind up deducting the flow here two, 298 00:15:23,160 --> 00:15:28,160 and reallocating it to this path here, 299 00:15:30,150 --> 00:15:31,800 so we're going to be able to flow 300 00:15:32,823 --> 00:15:35,950 two more units this way. 301 00:15:35,950 --> 00:15:37,610 We're gonna deduct two here. 302 00:15:37,610 --> 00:15:40,453 We're gonna add two here and add two here. 303 00:15:41,560 --> 00:15:46,560 And so this is a way of undoing the flow 304 00:15:47,260 --> 00:15:50,580 that we'd previously allocated to this edge 305 00:15:50,580 --> 00:15:53,350 so that we can use our resources better. 306 00:15:53,350 --> 00:15:57,240 So again, we're gonna wind up with something 307 00:15:57,240 --> 00:16:00,990 that looks like this, where we've deducted two here, 308 00:16:00,990 --> 00:16:02,670 we've added two here, 309 00:16:02,670 --> 00:16:04,340 we've deducted two here, 310 00:16:04,340 --> 00:16:05,910 we've deducted two here, 311 00:16:05,910 --> 00:16:07,460 we've added two here, 312 00:16:07,460 --> 00:16:10,750 we've deducted two here and added two here 313 00:16:10,750 --> 00:16:13,033 and this is our updated flow, 314 00:16:13,900 --> 00:16:17,270 and notice that the blocking flow problem 315 00:16:17,270 --> 00:16:21,170 that we had before, is now no problem at all okay? 316 00:16:21,170 --> 00:16:24,300 We've found a flow of six. 317 00:16:24,300 --> 00:16:25,760 That's the maximum flow. 318 00:16:25,760 --> 00:16:28,130 We've got three and three out of the source. 319 00:16:28,130 --> 00:16:31,140 We've got four and two into the sink, 320 00:16:31,140 --> 00:16:36,140 and we have avoided this problem of a blocking flow 321 00:16:37,330 --> 00:16:42,113 by using these backward edges in our residual graph. 322 00:16:43,070 --> 00:16:46,270 And so we arrive at that correct maximum flow now. 323 00:16:46,270 --> 00:16:48,320 Now we look at the residual graph 324 00:16:48,320 --> 00:16:50,910 and even considering the backward edges, 325 00:16:50,910 --> 00:16:54,750 now there really are no more augmenting paths from s to t. 326 00:16:54,750 --> 00:16:56,000 And so we're done. 327 00:16:56,000 --> 00:16:57,743 The algorithm terminates. 328 00:17:00,920 --> 00:17:03,270 To summarize how Ford-Fulkerson works, 329 00:17:03,270 --> 00:17:07,450 we initialize the flow network to all zeros. 330 00:17:07,450 --> 00:17:10,750 We initialize the residual network with weights 331 00:17:10,750 --> 00:17:14,290 on forward edges to correspond to the capacities. 332 00:17:14,290 --> 00:17:18,140 And we initialize the weights on the backward edges to zero. 333 00:17:18,140 --> 00:17:22,100 And then while augmenting paths exist in the residual graph 334 00:17:22,100 --> 00:17:24,350 and that's including the forward and backward edges, 335 00:17:24,350 --> 00:17:27,890 we just do the algorithm like we just did. 336 00:17:27,890 --> 00:17:31,050 We update the flow network by adding the augmenting flow 337 00:17:31,050 --> 00:17:33,000 to the corresponding edges. 338 00:17:33,000 --> 00:17:35,960 We update the forward edges in the residual network 339 00:17:35,960 --> 00:17:37,940 by deducting the augmenting flow 340 00:17:37,940 --> 00:17:39,720 from the corresponding edges. 341 00:17:39,720 --> 00:17:43,249 And we update the backward edges in the residual network 342 00:17:43,249 --> 00:17:46,170 by adding the augmenting flow to the corresponding edge. 343 00:17:46,170 --> 00:17:49,263 Now everything else I told you is true. 344 00:17:50,540 --> 00:17:52,380 Is this a greedy algorithm? 345 00:17:52,380 --> 00:17:56,090 Yes, it's still greedy, why? 346 00:17:56,090 --> 00:17:59,460 Because even though we've added this undo feature 347 00:17:59,460 --> 00:18:02,090 and coded in there your residual graph, 348 00:18:02,090 --> 00:18:05,110 we still proceed by finding augmenting paths 349 00:18:05,110 --> 00:18:08,090 and adding them in a greedy fashion to our solution. 350 00:18:08,090 --> 00:18:10,740 So once we've added an augmenting path, 351 00:18:10,740 --> 00:18:13,500 we never remove it from our solution. 352 00:18:13,500 --> 00:18:15,853 So it is still a greedy algorithm. 353 00:18:16,690 --> 00:18:18,723 The complexity remains the same, 354 00:18:19,600 --> 00:18:23,087 and again, with Ford-Fulkerson, 355 00:18:23,087 --> 00:18:26,250 we don't specify how we find augmenting paths. 356 00:18:26,250 --> 00:18:28,150 We just say, find augmenting paths. 357 00:18:28,150 --> 00:18:32,113 So the order has a certain arbitrariness to it. 358 00:18:33,160 --> 00:18:35,817 Now I mentioned in a previous video 359 00:18:35,817 --> 00:18:38,290 the Edmonds-Karp algorithm. 360 00:18:38,290 --> 00:18:41,250 And Edmonds-Karp is a modification 361 00:18:41,250 --> 00:18:45,570 of a Ford-Fulkerson that specifies how we find 362 00:18:45,570 --> 00:18:46,620 the augmenting paths. 363 00:18:46,620 --> 00:18:48,640 And if we use breadth-first search, 364 00:18:48,640 --> 00:18:51,550 then this is called the Edmonds-Karp algorithm. 365 00:18:51,550 --> 00:18:54,160 And the worst case complexity is a little different. 366 00:18:54,160 --> 00:18:56,350 It's big O of the cardinality V times 367 00:18:56,350 --> 00:18:59,020 the cardinality of E squared. 368 00:18:59,020 --> 00:19:04,020 It is in large part the same algorithm as Ford-Fulkerson. 369 00:19:04,410 --> 00:19:09,410 It just specifies how we discover the edges. 370 00:19:09,720 --> 00:19:12,300 So what haven't we discussed? 371 00:19:12,300 --> 00:19:15,333 Well, we haven't discussed reals. 372 00:19:15,333 --> 00:19:18,790 Our weights could have real values. 373 00:19:18,790 --> 00:19:22,120 They could be rational or irrational-valued capacities. 374 00:19:22,120 --> 00:19:24,723 We've only looked at integral capacities. 375 00:19:25,900 --> 00:19:28,080 And you should be aware that networks 376 00:19:28,080 --> 00:19:30,860 can have real valued capacities. 377 00:19:30,860 --> 00:19:33,300 We haven't given any proof of correctness 378 00:19:33,300 --> 00:19:35,410 nor when we're in this class. 379 00:19:35,410 --> 00:19:37,900 And we haven't talked about special applications 380 00:19:37,900 --> 00:19:39,510 of network flow. 381 00:19:39,510 --> 00:19:41,930 And you might be surprised to find 382 00:19:41,930 --> 00:19:45,510 that we can solve bipartite matching problems. 383 00:19:45,510 --> 00:19:49,380 You remember we talked about bipartite matchings 384 00:19:49,380 --> 00:19:51,000 in an earlier video. 385 00:19:51,000 --> 00:19:54,800 We can solve certain bipartite matching problems 386 00:19:54,800 --> 00:19:57,720 by using this network flow algorithm. 387 00:19:57,720 --> 00:20:00,080 And that might come as a bit of a surprise. 388 00:20:00,080 --> 00:20:02,280 But if you take a CS 224, 389 00:20:02,280 --> 00:20:05,993 which I recommend that's the algorithm design and analysis, 390 00:20:06,830 --> 00:20:08,440 you'll see all of these things. 391 00:20:08,440 --> 00:20:10,920 So that wraps up our discussion 392 00:20:10,920 --> 00:20:15,550 of max flow, min cut and Ford-Fulkerson. 393 00:20:15,550 --> 00:20:18,940 So in subsequent videos, we will move on 394 00:20:18,940 --> 00:20:23,240 to discuss the last topic that we will cover in this class 395 00:20:23,240 --> 00:20:25,950 and that's called minimum spanning trees. 396 00:20:25,950 --> 00:20:27,433 That's all for now, thanks.