Motivation and mathematical model
Think of a directed network of pipes carrying oil from a source to a refinery. Each pipe has a maximum rate it can sustain. The maximum flow problem asks for the largest rate that can be sent from a source node s to a sink node t.
The input is a directed graph G=(V,A). Each arc (i,j) has a nonnegative capacity u(i,j). A solution gives a flow value f(i,j) for every arc.
Maximum flow problem
Input
- Directed graph G=(V,A).
- Source s and sink t.
- Capacity u(i,j) ≥ 0 for each arc.
Feasible solution
- 0 ≤ f(i,j) ≤ u(i,j) for every arc.
- For every node except s,t, total flow in equals total flow out.
Goal
Maximize the flow value, i.e. the net flow into the sink.
The editor below also reports net flow into the sink, so it remains meaningful even if a user temporarily creates arcs leaving t.
Chapter example input
capacitiesTowards an algorithm: improving a feasible flow
Ford–Fulkerson is an improving algorithm. It starts with a feasible flow, such as the all-zero flow, and repeatedly finds a way to increase the value while preserving capacity constraints and flow conservation.
If every arc on an s-to-t path has unused capacity, we can increase the flow on every arc of that path by the same amount. The largest safe amount is the minimum unused capacity along the path.
Why the residual graph is needed
Sometimes an improvement requires decreasing flow on an arc that was used earlier. The residual graph records both possibilities:
- A forward residual arc (i,j) exists when f(i,j) < u(i,j); its residual capacity is u(i,j)-f(i,j).
- A backward residual arc (j,i) exists when f(i,j) > 0; its residual capacity is f(i,j).
Augmenting along a backward residual arc means decreasing the original flow on the corresponding input arc.
Ford–Fulkerson algorithm
- Start with a feasible flow f.
- Construct the residual graph Gf.
- Find an s-to-t path in Gf. If none exists, stop.
- Let δ be the minimum residual capacity on that path.
- Increase flow by δ on forward arcs and decrease flow by δ on backward arcs. Repeat.
To find a residual path, the chapter notes that one can reuse a shortest-path routine by giving every residual arc length 0. The lab uses BFS or DFS, which are equivalent reachability routines for this purpose.
Interactive Ford–Fulkerson lab
Use the chapter network or create a new directed graph. The left panel shows the original flow network with labels f/u. The right panel shows the residual graph; labels ending in F are forward residual arcs, and labels ending in B are backward residual arcs.
Flow network
labels are f/uResidual graph Gf
F = forward, B = backwardSelected item
Current step
Status
Arc residual capacities
| Arc | f/u | forward | backward |
|---|
Node flow balance
| Node | In | Out | In − Out |
|---|
Algorithm log
Upper bounds, cuts, and optimality certificates
A cut partitions the node set into S and T, with s∈S and t∈T. The capacity of the cut is the sum of capacities of arcs that leave S and enter T.
capacity(S,T) = ∑(i,j)∈A, i∈S, j∈T u(i,j)Every cut capacity is an upper bound on the value of every feasible flow. When Ford–Fulkerson terminates, take S to be the nodes reachable from s in the final residual graph. The resulting cut capacity equals the final flow value, proving optimality.
Cut playground
green arcs cross S → TChoose S
The source is always in S; the sink is always in T.
Crossing arcs: none
Why the final cut proves optimality
If no residual path from s to t exists, let S be all nodes reachable from s in the residual graph. Any original arc from S to T must be saturated; otherwise it would appear as a forward residual arc. Any original arc from T back to S must carry zero flow; otherwise its backward residual arc would make its tail reachable. Therefore the net flow across the cut equals the cut capacity.
Integrality property
If all capacities are integers and Ford–Fulkerson starts from the all-zero flow, every residual capacity is an integer at every step. Each augmentation uses the minimum residual capacity on a path, so the augmentation amount is also an integer. The algorithm therefore maintains integer flow values throughout.
Integrality property of max flow
When every capacity u(i,j) is integer, there exists a maximum flow with integer values on every arc. Ford–Fulkerson, started from the all-zero flow and using integer arithmetic, finds such a maximum flow.
The lab marks whether the current capacities are integer. Try changing one capacity to a fractional value and observe that the residual capacities and possible bottlenecks may become fractional as well.
