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.
How it works
Fill the streets
-
Choose source and sink
Pick a situation – the stadium emptying, rush hour, roadworks – or click any two junctions.
-
Pick an algorithm
Ford–Fulkerson, Edmonds–Karp, Dinic or MPM. Each street shows its flow over capacity, in vehicles per hour per direction.
-
Watch augmenting paths
Flow pours along each path the algorithm finds; the residual network, BFS levels and blocking flows appear in the inspector.
-
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.
What you learn
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
Keep exploring
More to try
-
Learn
Pathfinding Visualizer
Explore how classic graph algorithms navigate a real Procedity city.
-
Learn
Spanning Trees
Link every junction with the least street – Kruskal, Jarník, Borůvka and Edmonds step by step on a real neighbourhood.
-
Learn
Minimum Cut
Where is the street network weakest? Stoer–Wagner, Karger and the Gomory–Hu tree split a real city.
-
Game
Find the car
One car in town has a colour no other car has. Spot it in traffic as fast as you can.