Maximum flow

O(V·E²)

A flow network has a source, a sink, and directed edges each with a capacity — think pipes of different widths. Maximum flow asks how much can travel from source to sink at once without exceeding any pipe. Edmonds-Karp (the BFS version of Ford-Fulkerson) repeatedly finds a shortest augmenting path — a source→sink route that still has spare capacity in the residual graph — and pushes as much flow as its tightest edge allows. Crucially it also adds reverse capacity, so a later path can cancel earlier flow if that frees up a better route. It stops when no augmenting path remains, and by the max-flow min-cut theorem the total then equals the cheapest set of pipes that, if cut, would disconnect source from sink. Each edge shows flow/capacity; the path being pushed is highlighted. Using BFS bounds it at O(V·E²).

Directed graph

Edit the input and press Play

Loop

How it works

Start with zero flow; every edge shows 0 / capacity.
BFS the residual graph for a shortest source→sink path with spare capacity.
Push flow equal to the smallest residual capacity along that path.
Update residuals (including reverse edges) and repeat until no path remains.

Pseudocode

1edmondsKarp(graph, source, sink):   # O(V·E²)2  residual ← capacities; flow ← 03  while a path source→sink exists in the residual (BFS):4    b ← min residual capacity along that path5    for each edge u→v on the path:6      residual[u][v] −= b;  residual[v][u] += b7    flow ← flow + b8  return flow                         # = min cut