Maximum Flow
BACK: Shortest Path Algorithms
Suppose I’m Amazon and Prime is stressing me out. I have a bunch of warehouses all over California and I want to ship things from one warehouse (source \(s\)) to another warehouse (sink \(t\)). I have different trucks heading out to different locations and trucks leaving those locations–where each truck can hold a different capacity. Maximum flow seeks to maximize the amount going into the sink without overflowing out of the source. We need to make sure we don’t go over the bottleneck of what our sink can handle, based on the network of trucks.
Ford Faulkerson
Essentially, we want to find a path from the source to the sink, calculate it’s bottleneck, and then update the edge values accordingly to add up how much we pushed from the source to the sink. We can also pick paths which go backward, but in that case we would subtract from the edge cost. All edge costs must be nonnegative, so we would also need to consider this in the bottleneck calculation. We repeat this until there are no more paths that exist in the flow network.