Ford-Fulkerson

Computes the maximum flow in a flow network.

Original network

Residual network

Step 1 of 8

Find max flow from "s" to "t" using Edmonds-Karp (BFS). All flows start at 0.

Max Flow

Augmenting Path

—

Bottleneck

—

▶Algorithm

flow = 0; initialise residual graph
while augmenting path P exists:
P ← find path from s to t
bottleneck = min residual cap on P
augment flow along P by bottleneck
flow += bottleneck
return flow  // no more augmenting paths

Legend

Source / Sink

On path

Saturated edge

Forward edges: flow/capacity.
Green edges: backward residual (return-flow capacity).

1 / 8Speed