Flow Networks

Maximum Flow

Determine the maximum volume of "data" or "fluid" that can travel from source (S) to sink (T). Edmonds-Karp uses BFS to find augmenting paths in the Residual Graph until no capacity remains.

Time ComplexityO(V E²)

OptimizationEdmonds-Karp

Try Interactive Simulator

Residual Capacity

Every edge has a residual capacity (limit - current flow). We can only send flow through edges where residual capacity > 0.

Augmenting Paths

An augmenting path is a simple path from S to T in the residual graph. We "augment" the flow by the bottleneck capacity of this path.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join

Loading Lab...

Flow Networks

Maximum Flow

Determine the maximum volume of "data" or "fluid" that can travel from source (S) to sink (T). Edmonds-Karp uses BFS to find augmenting paths in the Residual Graph until no capacity remains.

Time ComplexityO(V E²)

OptimizationEdmonds-Karp

Try Interactive Simulator

Residual Capacity

Every edge has a residual capacity (limit - current flow). We can only send flow through edges where residual capacity > 0.

Augmenting Paths

An augmenting path is a simple path from S to T in the residual graph. We "augment" the flow by the bottleneck capacity of this path.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join

Network Flow

Network Flow

Maximum Flow

Residual Capacity

Augmenting Paths

Maximum Flow

Residual Capacity

Augmenting Paths