Learn · Maximum Flow

How many cars an hour can cross the city?

Every street can carry only so many cars an hour. Push traffic from the stadium to the motorway and the network fills up until one bottleneck says no more. This lab finds that limit – the maximum flow – on the streets of a generated city.

Maximum Flow on a procedurally generated 3D city (seed 77)
Free · in your browser AlgorithmsMax flowFord–FulkersonDinicInteractive

Fill the streets

  1. Choose source and sink

    Pick a situation – the stadium emptying, rush hour, roadworks – or click any two junctions.

  2. Pick an algorithm

    Ford–Fulkerson, Edmonds–Karp, Dinic or MPM. Each street shows its flow over capacity, in vehicles per hour per direction.

  3. Watch augmenting paths

    Flow pours along each path the algorithm finds; the residual network, BFS levels and blocking flows appear in the inspector.

  4. Find the bottleneck

    At the end the saturated streets form the minimum cut. Close one and see the city's capacity drop by exactly its capacity.

Augmenting paths, levels and blocking flow

Ford–Fulkerson keeps finding any path with spare capacity – and the lab can let an adversary pick the worst one, so you see why it can be painfully slow. Edmonds–Karp always takes the shortest path and fixes that. Dinic builds BFS levels and sends a blocking flow through them at once; MPM pushes through the node with the least throughput.

All four end with the same number, and the max-flow min-cut theorem says why: the most traffic you can push across equals the capacity of the weakest set of streets that separates the two places.

Maximum Flow at a glance

Algorithms
Ford–Fulkerson, Edmonds–Karp, Dinic, MPM
Capacities
Real lane capacities of each street, in vehicles per hour
Shows
Residual network, BFS levels, augmenting paths, pseudocode