← Graphs & Trees

Ford-Fulkerson

Computes the maximum flow in a flow network.

Original network
0/100/100/60/80/12sABt
Residual network
10106812sABt

Step 1 of 8

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

Max Flow

0

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