Maximum Flow Problem Definition
What you'll learn: You'll understand what the maximum flow problem asks us to solve in a flow network.
Now that you've learned about flow networks, residual networks, augmenting paths, and the max-flow min-cut theorem, let's formally define the problem we're trying to solve.
The Core Problem
Given a flow network with:
- A source node (where flow originates)
- A sink node (where flow terminates)
- Edges with capacities (maximum flow each edge can carry)
- Flow conservation at all intermediate nodes (flow in = flow out)
The maximum flow problem asks: What is the largest amount of flow we can push from the source to the sink while respecting all capacity constraints?
Understanding the Goal
Think of water pipes connecting a water tower (source) to a city (sink). Each pipe has a maximum capacity. Some pipes connect to intermediate junctions. The question is: How much water can we deliver to the city?
We want to find a valid flow (satisfying capacity and conservation constraints) where the total flow leaving the source—which equals the total flow entering the sink—is as large as possible.
What Makes It a Problem?
The challenge is that paths from source to sink share edges. Sending more flow along one path might "use up" capacity that could have been better utilized by a different combination of paths. The maximum flow problem requires finding the optimal way to distribute flow across all possible paths.
Key Takeaway: The maximum flow problem asks us to find the largest total flow we can send from a source node to a sink node in a flow network while respecting all edge capacities and flow conservation constraints.