Ford-Fulkerson: Max Flow

[00:00:00]
>> We're gonna go on we're gonna do one more graph algorithm. I'm very excited about this graph algorithm It's called Ford-Fulkerson. Has anyone heard of Ford-Fulkerson? Well, you can say Fulkerson like Fulkerson it just sounds fun. I don't know what it is about it but it's a great one.

[00:00:13]
This one is called max flow min cut, all right? There the same problem in some sense. It's very, very exciting. And I have this little note right here and I kid you not it literally says car algo British people. That's what it says because it's very fantastic I'll explain that one sec.

[00:00:34]
I just want to leave you guys with that one because it's super exciting. All right, so I have this really I actually have one right here that's super good. So, we'll do this I know, car algorithm British people, classic phrase you hear on the regular. Now, usually whenever we're doing a max flow problem, they always are directed graphs, right?

[00:00:56]
It would be kinda weird to try to do an undirected situation going on here but in some sense they're also undirected graphs. Now you're probably hearing that going well that doesn't make much more sense that makes frankin sense I'm gonna put a 0/10, 0/8, 0/5, 0/5, 0/5, 0/8 did I get that right?

[00:01:29]
I guess it really didn't matter 0/6, 0/8 hold on one second, there's a little bit of setup to this. All right, a maximum flow problem usually starts off with something called a source. We pretend the source has an infinite input. It can just keep on putting stuff into the graph.

[00:01:46]
We have a sync our destination. Where do we want to go? T for sync, of course, because well source and sync I mean just really truly unfortunate. And you also didn't use any other letters from the word sync it's t, okay? That's just what we do here. You'll notice that instead of having a weight, we have a weight with like a zero on it.

[00:02:05]
And so what that means is that's how much flow is in this current point. Now, okay people are saying t or terminal or terminus. Okay, tough guy I'm gonna say t for sync. Okay, and so our goal is try to maximize the flow through this network. You can imagine this could be used for networks.

[00:02:23]
Remember how I said I'll graph problems come down to networks. We can imagine that's what you're trying to do is try to figure that out or traffic, traffic is kinda like another way you could do something as they have to figure out how to get enough stuff through.

[00:02:34]
The Ford-Fulkerson algorithm does not specify how you choose a path from s to t that's like choose your own adventure. You could do a depth-first search, you could do a breadth-first search, there's something called Dynex algorithm. You could do all sorts of different stuff we're just gonna keep it simple and I'm just gonna draw a path, okay?

[00:02:52]
I have eyeballs, I'm pretty good at making paths for stuff in order to kinda choose a path. Eventually you will hit a maximum flow. So let's just start kind of by example. So I'm gonna choose this top route right here, very simple. And then what you do is you find the minimum flow throughout that top route.

[00:03:12]
I have a seven, ten, eight. It's obviously a seven that means I can use seven units of flow right here, I can use seven units of flow right here and I can use seven units of flow right here. Next, we'll choose this one. I can choose a, this one has a here, I'm gonna erase this and I'm just gonna reuse these lines again.

[00:03:32]
This one has a flow of six, this one has a flow of eight, this one has a flow of one. There's only one unit left in this in this pipe so that means we can use one. So I could draw a little one right here, I could draw a little one right here and I can draw an 8 right here we've maximized our flow right there.

[00:03:49]
Well we still have another side so I can do a five, five, ten our minimum flow or our maximum flow we can get through this is five, right? Because this is our smallest pipe right here, all right, five, five, five. And so there's no other path left in this graph because if I try to go up here, it's already full.

[00:04:11]
If I try to go over here, you can't get to this node without going through this one which is already full. So therefore, this is our max flow of the graph which is 13. That is our maximum flow, which our minimum cut of the graph is also 13.

[00:04:27]
And a cut is defined in how do you remove, how do you break apart the graph such that the source and the sync can no longer touch. They're no longer in the same sub graph. So that's called the minimum cut, the minimal amount of value you can cut through this.

[00:04:44]
I'll show you what that means here in a moment that's the whole car British people thing that I was talking about but keep that in mind, okay,