Network Flow: Ford-Fulkerson, Edmonds-Karp, Dinic & Min-Cost Flow
Why this exists
Some problems are about moving stuff: oil through pipes, packets through links, trains through a rail network, workers into shifts. Every link has a capacity, and the question is how much can get from a source to a destination per unit time. Others look nothing like movement: which pixels are foreground, which projects to fund given their prerequisites, whether a sports team can still win its division, which edges to cut to disconnect two servers most cheaply. A surprising number of both kinds reduce to one problem — maximum flow — and its twin, minimum cut.
The history is telling. In 1955 T. E. Harris and F. S. Ross wrote a then-classified RAND report on the capacity of the Soviet rail network to Eastern Europe; what the US Air Force wanted was the bottleneck — the cheapest set of rail links whose destruction would sever it, i.e. the minimum cut. Lester Ford and Delbert Fulkerson took up the problem and in 1956 proved the max-flow min-cut theorem: the maximum flow equals the capacity of the minimum cut, so the two questions are one. Peter Elias, Amiel Feinstein and Claude Shannon proved the same theorem independently the same year in the context of communication networks. Ford and Fulkerson's augmenting-path method was not polynomial in general; Jack Edmonds and Richard Karp (1972) and, independently and earlier, Yefim Dinitz (1970, usually transliterated "Dinic") showed that choosing shortest augmenting paths fixes that. Goldberg and Tarjan's push-relabel (1988), Orlin's (2013) and the 2022 almost-linear-time algorithm of Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva continued the line.
Flow is the second half of a pair with the previous lesson: bipartite matching is max flow with unit capacities, König's theorem is max-flow min-cut in disguise, and the Hungarian algorithm is min-cost flow on a complete bipartite graph. This lesson builds the general machinery. In interviews flow appears rarely and usually as "can you recognise it?"; in competitive programming it is a staple; in industry it powers image segmentation, cluster schedulers, transport planning, airline crew and fleet assignment, and network reliability analysis.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "Maximum amount/rate from A to B", edges with capacities | Max flow (Dinic / Edmonds–Karp) |
| "Minimum total weight of edges to remove to disconnect s from t" | Min cut = max flow; recover the cut from the residual graph |
| "Maximum number of edge-disjoint paths" | Max flow with unit capacities |
| "Vertex-disjoint paths", "each node can be used at most k times" | Split each vertex into in/out with a capacity-k edge |
| "Several sources / several sinks" | Super-source and super-sink |
| "Each X assigned to at most c Y's, each Y takes at most d X's" | Bipartite flow: (cap c), (cap 1), (cap d) |
| "Choose a subset; picking A forces picking B; maximise profit" | Project selection = max-weight closure = min cut |
| "Label each item 0/1; per-item cost plus a penalty for neighbours that differ" | Min cut (image segmentation, Potts/Ising energies with two labels) |
| "Each edge must carry at least and at most ", "feasible circulation" | Lower bounds via demands and a super-source/sink |
| "Can team X still finish first?" | Baseball elimination network |
| "Max flow, but each unit on an edge costs money; minimise cost" | Min-cost max-flow (successive shortest paths with potentials) |
| "Assign n tasks to n workers at min cost", sparse or with capacities | Min-cost flow (Hungarian for the dense square case) |
| Binary search on the answer, then "is there a schedule/assignment?" | Feasibility check by max flow inside a binary search |
| a few hundred to a few thousand, in a contest | Flow is affordable; Dinic is the default |
The meta-trigger: something is conserved at intermediate nodes, and something is limited on edges or nodes. If you can say "what flows, from where, to where, and what limits it", you can build the network. If the problem asks for a minimum cut — a cheapest way to separate two things — max flow computes it.
Intuition & first principles
Flow networks
A flow network is a directed graph with a capacity on every edge, a source and a sink . A flow assigns to every edge with
- capacity constraint: ;
- flow conservation: for every , flow in equals flow out, .
The value is the net flow out of (equivalently into ). The max-flow problem asks for a flow of maximum value.
Think of water in pipes: capacities are pipe widths, conservation says junctions do not leak or store water, and the value is the rate at the tap. The analogy breaks in one useful way: flow has no physics, so it can be routed any way that respects the two constraints.
Cuts, and why they bound flow
An - cut partitions with and . Its capacity is the total capacity of edges from to (edges from to do not count):
Lemma (flow across any cut). For any flow and any cut , , the net flow across the cut. Proof: sum the conservation equations over all and add the definition of at ; every edge with both ends in appears once positively and once negatively and cancels.
Corollary (weak duality). for every flow and every cut, since and . So any flow value is a lower bound on the min cut and any cut capacity is an upper bound on the max flow. If you ever find a flow and a cut with equal values, both are optimal. The theorem below says you always can.
The residual graph: room to push, room to undo
Why not just repeatedly find an - path with spare capacity and push flow along it? Because early choices can be wrong. In the diamond , , , (all capacity 1) plus a cross edge (capacity 1), greedily pushing along saturates , and . Now is unreachable (its only way in is full) and has no exit, so no forward path remains: value 1, where 2 is possible. The fix is to allow undoing: pushing flow "backwards" along cancels flow already sent.
The residual graph encodes both. For each edge with flow :
- a forward residual edge with residual capacity (room to push more);
- a backward residual edge with residual capacity (room to cancel).
flowchart LR
subgraph Original["Edge in G: flow 3 of capacity 5"]
U1["u"] -->|"3 / 5"| V1["v"]
end
subgraph Residual["Residual graph G_f"]
U2["u"] -->|"2 more"| V2["v"]
V2 -->|"3 cancellable"| U2
end
An augmenting path is an - path in ; its bottleneck is the minimum residual capacity on it. Pushing the bottleneck along it increases forward flows and decreases flows on edges traversed backwards, and keeps the flow feasible. In the diamond, after the bad first path, the residual graph contains (using the backward edge ), and pushing 1 along it cancels the cross flow, reaching value 2.
Implementation note: store every edge together with its reverse in an edge array at indices and , so the partner of edge is e ^ 1. Pushing along is cap[e] -= δ; cap[e ^ 1] += δ. This handles antiparallel edges ( and both present) and parallel edges with no special cases — each original edge gets its own pair.
Mechanics
Ford–Fulkerson
Ford–Fulkerson is the method, not a specific algorithm: while has an augmenting path, push its bottleneck. With integer capacities each augmentation adds at least 1, so it terminates after at most augmentations, each costing with DFS: . That is pseudo-polynomial — it depends on capacity values, not just sizes. The classic bad case is the diamond above with capacities on the outer edges and 1 on the cross edge: a DFS that alternates between and needs augmentations of 1 each.
With irrational capacities it is worse: Ford–Fulkerson may not terminate at all, and the flow values it produces can converge to a limit strictly below the max flow. Ford and Fulkerson gave such an example in their 1962 book; Zwick (1995) found the smallest such networks, whose capacities involve the golden ratio. On computers with integer or rational capacities this cannot happen (rationals can be scaled to integers), but it shows that the path choice is what makes an algorithm, and it motivates the next two.
Edmonds–Karp: always the shortest augmenting path
Edmonds–Karp is Ford–Fulkerson with augmenting paths found by BFS, i.e. shortest in number of edges. That one choice makes the number of augmentations regardless of capacities, giving total.
Here is the network used in the trace and the visualiser (edge labels are capacities):
flowchart LR
s(("s")) -->|"4"| a(("a"))
s -->|"9"| b(("b"))
b -->|"3"| a
a -->|"9"| c(("c"))
a -->|"5"| d(("d"))
b -->|"5"| c
d -->|"6"| c
c -->|"6"| t(("t"))
d -->|"11"| t
Trace: Edmonds–Karp on the 6-vertex network
Computed by the trace generator (scripts/traces/edmonds_karp.py; BFS scans neighbours in vertex order s, a, b, c, d, t). Distances are BFS distances in the residual graph before that iteration's augmentation.
| Iter | Augmenting path | Edges | Bottleneck | Total | Newly saturated | |
|---|---|---|---|---|---|---|
| 1 | 0, 1, 1, 2, 2, 3 | s→a→c→t | 3 | 4 | 4 | s→a |
| 2 | 0, 2, 1, 2, 3, 3 | s→b→c→t | 3 | 2 | 6 | c→t |
| 3 | 0, 2, 1, 2, 3, 4 | s→b→a→d→t | 4 | 3 | 9 | b→a |
| 4 | 0, 3, 1, 2, 4, 5 | s→b→c⇢a→d→t | 5 | 2 | 11 | a→d (and a→c drops from 4 to 2) |
| 5 | 0, 3, 1, 2, ∞, ∞ | none | – | – | 11 | — |
Three things to notice:
- Iteration 4 uses a backward residual edge c⇢a. Path 1 sent 4 units along a→c; now 2 of them are cancelled. Net effect: the 2 units that b sends to c continue to t over c→t (which a no longer needs as much), and a's 2 freed units go a→d→t instead. No forward-only path from s to t exists at this point, yet the flow is not maximum.
- Distances never decrease. goes 1, 2, 2, 3; goes 3, 3, 4, 5, ∞. That monotonicity is the heart of the Edmonds–Karp bound (proved under Correctness).
- The final BFS gives the min cut for free. Vertices reachable from s in the last residual graph are . Edges from to are a→d (5) and c→t (6), total 11 — equal to the flow, so both are optimal. The edge d→c goes from to and does not count.
Final flows: s→a 4/4, s→b 7/9, b→a 3/3, a→c 2/9, a→d 5/5, b→c 4/5, d→c 0/6, c→t 6/6, d→t 5/11. Check conservation at c: in , out 6.
Dinic: level graphs and blocking flows
Edmonds–Karp runs a full BFS for every single path. Dinic's algorithm (Dinitz 1970) amortises it, exactly as Hopcroft–Karp does for matching:
- BFS from in to compute levels = shortest distance. If is unreachable, stop. The level graph keeps only residual edges with .
- Find a blocking flow in the level graph: a flow such that every - path in the level graph has at least one saturated edge. Use repeated DFS from , advancing only to the next level.
- Add it to and repeat.
flowchart TD
A["BFS from s in residual graph: compute level of every vertex"] --> B{"t reachable?"}
B -->|"no"| Z["done: flow is maximum; reachable set S is a min cut"]
B -->|"yes"| C["reset current-arc pointer it[v] = 0 for all v"]
C --> D["DFS from s along edges with level + 1 and residual capacity"]
D --> E{"reached t?"}
E -->|"yes, bottleneck x"| F["push x along the path"]
F --> D
E -->|"no path left"| A
Current-arc optimisation. Each vertex keeps a pointer it[v] into its adjacency list. When an edge out of turns out to be useless — saturated, or leading to a dead end — the pointer moves past it and the edge is never examined again in this phase. A DFS step either advances along an edge (at most steps per path, since levels strictly increase) or retires an edge; each path saturates at least one edge. So a blocking flow costs : at most paths of length , plus retirements. Without current arcs, Dinic can degrade badly; with them, it is the algorithm most competitive programmers keep in their library.
Why at most phases. After a blocking flow, every shortest - path in the old level graph contains a saturated edge, and the new residual edges (reverses of edges used) go from level to level — backwards — so they cannot create a path of the same length. The - distance strictly increases each phase and is at most . Total: .
On the trace network Dinic needs three phases instead of four BFS runs: phase 1 (levels s0, a1, b1, c2, d2, t3) pushes the blocking flow s→a→c→t (4) + s→b→c→t (2) = 6; phase 2 (t at level 4) pushes s→b→a→d→t (3); phase 3 (t at level 5) pushes s→b→c→a→d→t (2); total 11. On the classic six-vertex example from CLRS's flow chapter (max flow 23), Dinic needs two phases: a blocking flow of 16 at distance 3, then 7 at distance 4.
Unit networks. When every edge has capacity 1, a blocking flow is (each edge is saturated or retired once), and Even & Tarjan (1975) and Karzanov (1973) showed the number of phases is , and also for simple graphs. If additionally every vertex other than has a single incoming edge or a single outgoing edge — as in the bipartite matching network — there are phases, so Dinic runs in : it is Hopcroft–Karp.
Push-relabel, briefly
Augmenting-path algorithms keep a valid flow and look for paths. Push-relabel (Goldberg & Tarjan, 1988) keeps a preflow — vertices may hold excess inflow — and a height label per vertex. Excess is pushed downhill along residual edges; a vertex with excess and no downhill edge is relabelled (raised). Heights bound distances to (or back to ), which bounds the work: generic, with FIFO selection, with highest-label selection, and much faster in practice with the gap and global-relabelling heuristics. It is CLRS 3rd ed. §26.4–26.5 (dropped from the 4th edition) and cp-algorithms has a full implementation. In practice, highest-label push-relabel is often the fastest general-purpose max-flow code for large dense instances; Dinic is simpler and fast enough for almost all contest problems. For the grid graphs of computer vision, the Boykov–Kolmogorov algorithm (2004) — augmenting paths with search trees that are reused between iterations — is the standard.
Recovering the minimum cut
After any max-flow algorithm finishes, run one more BFS/DFS from in the residual graph. Let be the reachable set. Then is a minimum cut, and the cut edges are original edges with , — all saturated. For the trace network, that is with cut edges a→d and c→t. Edge cases worth knowing: the min cut need not be unique (the set reachable from gives the cut "closest" to ; the set that can reach in gives the one closest to ), and a min cut in an undirected graph is found by modelling each undirected edge as two directed edges with the same capacity.
Min-cost max-flow
Now each edge also has a cost per unit of flow, , and we want the maximum flow of minimum total cost (or a flow of a given value at minimum cost). Residual edges carry cost: forward , backward (cancelling a unit refunds its cost).
Successive shortest paths (SSP). Repeatedly find the cheapest augmenting path (shortest path by cost in ) and push its bottleneck. If the initial network has no negative-cost cycle, the residual network never gets one, and after each augmentation the flow is the cheapest among all flows of its value. Because residual graphs contain negative-cost backward edges, the first shortest-path computation needs Bellman–Ford or SPFA.
Potentials let you use Dijkstra after that. Keep a potential per vertex and work with reduced costs . Along any - path the reduced costs telescope to the true cost plus , a constant, so shortest paths are unchanged. Set to the shortest distances from (first from Bellman–Ford). Then every residual edge has (that is the triangle inequality ), and edges on shortest paths have — so after augmenting along a shortest path, the new backward edges also have . Non-negativity is preserved, Dijkstra applies, and after each Dijkstra we update . This is Johnson's reweighting from the shortest-paths lesson, reused at every iteration; Edmonds & Karp (1972) and Tomizawa (1971) introduced it for flows.
Small example: (cap 4, cost 1), (2, 5), (2, 1), (2, 6), (4, 1). Computed by the implementation below and checked by enumerating all integral flows:
| Aug | Cheapest path | Path cost | Bottleneck | Flow | Cost so far |
|---|---|---|---|---|---|
| 1 | s→a→b→t | 1 + 1 + 1 = 3 | 2 (a→b) | 2 | 6 |
| 2 | s→b→t | 5 + 1 = 6 | 2 (s→b) | 4 | 18 |
| 3 | s→a→t | 1 + 6 = 7 | 2 (a→t) | 6 | 32 |
Path costs are non-decreasing (3, 6, 7) — always true for SSP, and why you can stop early when you want "flow at minimum cost" or "any flow, minimum cost" (stop when the next path cost is ). Max flow 6 at cost 32.
Complexity: Bellman–Ford once, , then each augmentation is a Dijkstra, . The number of augmentations is at most the flow value (pseudo-polynomial), so . For the assignment problem , giving on a dense graph — close to Hungarian. Strongly polynomial alternatives exist (cycle canceling with minimum mean cycles, Goldberg–Tarjan cost scaling; Orlin's 1993 algorithm), and for large instances libraries use network simplex (LEMON's NetworkSimplex) or cost-scaling push-relabel (OR-Tools' min-cost flow).
Modelling tricks
Most of the skill in flow is building the network. The algorithms are library code.
Multiple sources and sinks
Add a super-source with an edge for each source (capacity = that source's supply, or ) and a super-sink likewise. Max flow from to answers the multi-source question.
Vertex capacities: split the vertex
Flow algorithms limit edges, not vertices. To cap vertex at , replace it by with capacity ; every edge into now enters and every edge out leaves . With on every internal vertex, max flow = maximum number of vertex-disjoint paths (Menger's theorem, vertex form), and the min cut tells you which vertices to remove to disconnect from .
flowchart LR
x["x"] -->|"cap 7"| vin["v_in"]
y["y"] -->|"cap 4"| vin
vin -->|"vertex cap k"| vout["v_out"]
vout -->|"cap 5"| z["z"]
vout -->|"cap 9"| w["w"]
Bipartite matching as flow
each left vertex (cap 1), each compatible pair left right (cap 1, or — same answer), each right vertex (cap 1). Integral max flow = maximum matching; the min cut's left vertices not in plus right vertices in form a minimum vertex cover — König's theorem from the previous lesson falls out of max-flow min-cut. Changing to capacity gives b-matching (each worker may take up to jobs).
Lower bounds and circulations
Suppose edge must carry between and units. Pre-send the mandatory : replace the edge by one of capacity , and record that has received extra and has sent extra. Let be the net mandatory inflow. Add a new source with an edge of capacity for each with positive excess, and with capacity for negative excess. For an - problem (rather than a pure circulation) also add with infinite capacity so flow can circulate. A feasible flow exists iff the max flow from to saturates every edge. To then maximise the - flow, remove the edge and the helper vertices and run max flow from to on the remaining residual graph (cp-algorithms, "Flows with demands"; Kleinberg & Tardos §7.7).
Project selection (maximum-weight closure)
Projects have profits (positive: revenue; negative: cost), and dependencies "taking requires taking ". Choose a dependency-closed set maximising total profit. Build: with capacity for each ; with capacity for each ; with capacity for each dependency. Then
and the chosen projects are the side of the min cut. Why: a finite cut cannot separate from a prerequisite (that edge is ), so is closed. Its capacity is (positive profits you gave up: ) + (costs you pay: ), and minimising it maximises profit. This is Picard (1976); Kleinberg & Tardos §7.11.
Example (verified by brute force in the code below): mobile app +12 requiring API (−4) and database (−5); analytics +6 requiring database and data pipeline (−7). Sum of positives 18; min cut 15; best profit 3, choosing app, API and database. Analytics is not worth it: it would add 6 but cost 7 for the pipeline.
flowchart LR
s(("s")) -->|"12"| app["app +12"]
s -->|"6"| ana["analytics +6"]
app -->|"inf"| api["API -4"]
app -->|"inf"| db["database -5"]
ana -->|"inf"| db
ana -->|"inf"| pipe["pipeline -7"]
api -->|"4"| t(("t"))
db -->|"5"| t
pipe -->|"7"| t
Image segmentation (two-label energy minimisation)
Each pixel gets a cost for being labelled foreground and for background, and each pair of neighbouring pixels pays if they get different labels (smoothness). Minimise the total. With the convention " side = foreground", put capacity on (cut exactly when ends up background) and on (cut exactly when is foreground), plus edges and with capacity each. Every labelling is a cut and its capacity is exactly the energy, so the min cut is the optimal labelling. Greig, Porteous and Seheult (1989) showed this computes exact MAP estimates for binary images; Boykov, Veksler and Zabih extended it with α-expansion to many labels (approximately), and "graph cuts" became a standard tool in vision. It only works for energies that are submodular (penalising disagreement, never rewarding it) — Kolmogorov & Zabih (2004) characterised exactly which binary energies are graph-representable. Kleinberg & Tardos §7.10.
Baseball elimination
Team is eliminated if no outcome of the remaining games lets it finish with at least as many wins as every other team. Assume wins all its remaining games, reaching . For the other teams, build: (game node ) with capacity = games left between and ; game node and with ; team node with capacity (how many more wins can afford). Team survives iff the max flow saturates all source edges — all remaining games can be assigned winners without anyone overtaking . If not, the team nodes on the side of the min cut form a certificate with : on average they must win more than (Schwartz 1966; Kleinberg & Tardos §7.12).
Example (computed by the code below): wins and remaining games — Atlanta 83 wins (games left: 1 vs Philadelphia, 6 vs New York, 1 vs Montreal), Philadelphia 80 (1 vs Atlanta, 2 vs Montreal), New York 78 (6 vs Atlanta), Montreal 77 (1 vs Atlanta, 2 vs Philadelphia). Montreal is trivially out: . Philadelphia can reach 83 — tying Atlanta — but is still eliminated: Atlanta and New York together have wins and 6 games left between them, so on average they end with , and one of them must exceed Philadelphia. The min cut finds exactly . New York (max 84) survives.
Other standard reductions
- Edge-disjoint paths (Menger, edge form): unit capacities, max flow = number of paths; decompose the flow into paths by walking saturated edges from .
- Airline / vehicle scheduling (Kleinberg & Tardos §7.9): each flight is an edge from its departure node to its arrival node with lower bound 1; an edge from flight 's arrival to flight 's departure if one plane can fly both in sequence; source and sink edges represent planes. Feasibility with planes is a circulation with demands. Minimising planes is the DAG path cover of the previous lesson.
- Survey design / bounded assignment (K&T §7.8): customers ask about products, each customer between and questions, each product between and responses — a bipartite flow with lower bounds.
- Binary search + flow: "maximise the minimum..." or "minimum time such that all jobs finish" — guess the answer, build the network for that guess, check whether max flow reaches the demand.
The ladder: brute force → better → optimal
Rung 1: enumerate cuts —
By the theorem, max flow = min cut, so try every , and take the cheapest. Exponential, but the right oracle for random testing up to (the throwaway tests for this lesson did exactly that).
Rung 2: Ford–Fulkerson with DFS —
Correct and simple; fast when the answer is small (unit capacities, : ). Dangerous when capacities are large: augmentations on the four-vertex counterexample. Capacity scaling (push only paths with bottleneck , halving ) improves it to .
Rung 3: Edmonds–Karp —
BFS path selection makes the bound independent of capacities. Fine for a few hundred. Easy to get right, which is why it is the textbook choice and a good interview answer.
Rung 4: Dinic — , on unit networks
One BFS per phase, blocking flow by DFS with current arcs. In practice much faster than its bound: the C++ implementation on this page took 11–13 ms on random networks with , and capacities up to (one machine, three seeds; adversarial inputs can be much slower). The default.
Rung 5: push-relabel with heuristics —
Highest-label with gap relabelling and global relabelling. Faster than Dinic on many large dense instances; more code. Asymptotically better algorithms (Orlin , almost-linear 2022) exist but are not what people run.
| Rung | Time | Depends on capacities? | Space | Use when |
|---|---|---|---|---|
| Enumerate cuts | no | testing only | ||
| Ford–Fulkerson (DFS) | yes (pseudo-poly) | small answers, unit capacities | ||
| Capacity scaling | logarithmically | huge capacities, simple code | ||
| Edmonds–Karp | no | small graphs, interviews | ||
| Dinic | ; unit: | no | default for contests and tools | |
| Push-relabel (HL + gap) | no | large dense instances | ||
| SSP min-cost flow (Dijkstra + potentials) | yes () | min-cost, moderate flow value |
Correctness
Max-flow min-cut theorem
Theorem (Ford & Fulkerson 1956; Elias, Feinstein & Shannon 1956). For a flow in a network, the following are equivalent:
- is a maximum flow;
- the residual graph has no augmenting path;
- for some cut .
Proof. (1 ⇒ 2) If an augmenting path existed, pushing its bottleneck (positive) would increase .
(2 ⇒ 3) Let be the set of vertices reachable from in , and . By (2), , so is a cut. For an edge with , : if , the forward residual edge would make reachable, so . For an edge with , : if , the backward residual edge would make reachable, so . By the flow-across-a-cut lemma, .
(3 ⇒ 1) By weak duality every flow has value .
The proof is constructive: the reachable set from the final residual graph is a minimum cut, which is why min-cut recovery is one BFS.
Integrality theorem. If all capacities are integers, Ford–Fulkerson (and so Edmonds–Karp and Dinic) produces an integer-valued maximum flow, since every bottleneck is an integer. This is what makes flow usable for combinatorial problems: "one unit of flow on edge " can mean "worker takes job ", and fractional solutions never need rounding. It also proves König, Menger and Hall as corollaries.
Edmonds–Karp: distances are monotone, edges become critical rarely
Let be the BFS distance from to in .
Lemma 1 (monotonicity; CLRS 3rd ed. Lemma 26.7). After each Edmonds–Karp augmentation, does not decrease for any .
Sketch. Suppose an augmentation from to decreases some distance; pick with the smallest among such vertices, and let be its predecessor on a shortest - path in , so and, by the choice of , . If the edge was already in , then , contradiction. Otherwise appeared because the augmentation pushed flow along , which (being on a BFS shortest path) means , hence , again a contradiction.
Lemma 2. Each edge is critical (it is the bottleneck, so it disappears from ) at most times. When is critical, . For it to be critical again, flow must first be pushed along , at which point by monotonicity. So between consecutive critical moments rises by at least 2, and it is at most while is reachable.
Bound. There are residual edges, each critical times, and every augmentation has a critical edge: augmentations, each an BFS — .
The trace shows Lemma 1 in action ( = 3, 3, 4, 5, then unreachable) and Lemma 2's mechanism: a→c becomes partly cancelled only once has grown from 1 to 3.
Dinic
Phases. Let be the level of . After the blocking flow, every - path of length in used only level-graph edges and contained a saturated edge, which is gone. New residual edges are reverses of level-graph edges, going from level to level . Any - path in the new residual graph either uses only old level-graph edges (impossible at length : each such path has a saturated edge) or uses at least one edge that does not go up a level, so its length is at least . Hence strictly increases, and there are at most phases.
Blocking flow cost. With current arcs, each DFS that reaches costs for the path plus the edges it retires, saturates at least one edge, and retired edges are never revisited in the phase. So per phase and overall. For unit capacities each edge is saturated or retired once per phase, per phase; the phase bound for unit networks follows the Hopcroft–Karp counting argument: after phases the remaining flow decomposes into vertex-disjoint paths of length , so at most units remain (Even & Tarjan 1975).
Successive shortest paths
Invariant: the current flow has minimum cost among all flows of value , equivalently (the negative cycle optimality criterion) has no negative-cost cycle. Initially and the original network has no negative cycle by assumption. Augmenting along a shortest path preserves "no negative cycle": with potentials = shortest distances, all residual edges have reduced cost , the path edges have reduced cost 0, and their reverses therefore also have reduced cost 0; a graph with all reduced costs has no negative cycle (reduced costs around a cycle sum to its true cost). The flow optimality criterion itself is a standard LP-duality result (Ahuja, Magnanti & Orlin, Network Flows, ch. 9; Kleinberg & Tardos §7.13 for the matching case). Integrality carries over: with integer capacities SSP returns an integral min-cost flow.
Complexity
| Algorithm | Time | Notes |
|---|---|---|
| Ford–Fulkerson | may not terminate with irrational capacities | |
| Edmonds–Karp | augmentations × BFS | |
| Dinic | unit capacities; unit networks | |
| Push-relabel (FIFO / highest label) | / | gap + global relabel heuristics matter in practice |
| Orlin (2013) | theoretical; combines King–Rao–Tarjan with compact networks | |
| Chen et al. (2022) | theoretical; interior-point method with dynamic data structures | |
| Min cut recovery | one BFS after max flow | |
| SSP min-cost flow | Bellman–Ford once, then Dijkstra with potentials |
Space is for all of them with the paired edge array (each original edge stores two residual entries).
Constants matter more than the bounds suggest. Dinic's worst case is rarely approached: on random and contest graphs the number of phases is small and blocking flows are found quickly. Measured with this page's C++ Dinic: a random bipartite matching network with vertices and edges solved in 23 ms. Storing edges in flat arrays (to, cap, next or CSR offsets) instead of objects in lists improves cache locality markedly; in Python, flow on more than about edges is slow, and for real work you would call a library — NetworkX (pure Python, convenient), OR-Tools' SimpleMaxFlow and SimpleMinCostFlow (C++), or the LEMON and Boost Graph libraries.
Implementation
Edmonds–Karp (canonical)
Edges are stored in arrays with the reverse of edge e at e ^ 1. Every block uses the same tests: the trace network (11), the classic six-vertex CLRS-style network (23), a network with no - path (0), parallel edges, and antiparallel edges.
from collections import deque
class EdmondsKarp:
def __init__(self, n: int):
self.n = n
self.adj = [[] for _ in range(n)] # adj[u] = list of edge ids
self.to: list[int] = []
self.cap: list[int] = []
def add_edge(self, u: int, v: int, c: int) -> int:
self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)
return len(self.to) - 2 # id of the forward edge
def max_flow(self, s: int, t: int) -> int:
flow = 0
while True:
par_edge = [-1] * self.n
par_edge[s] = -2
q = deque([s])
while q and par_edge[t] == -1: # BFS: shortest augmenting path
u = q.popleft()
for e in self.adj[u]:
v = self.to[e]
if par_edge[v] == -1 and self.cap[e] > 0:
par_edge[v] = e
q.append(v)
if par_edge[t] == -1:
return flow
b, v = float("inf"), t # bottleneck
while v != s:
e = par_edge[v]
b = min(b, self.cap[e])
v = self.to[e ^ 1]
v = t
while v != s: # push b; the reverse edge gains b
e = par_edge[v]
self.cap[e] -= b
self.cap[e ^ 1] += b
v = self.to[e ^ 1]
flow += b
def build(n, edges):
g = EdmondsKarp(n)
for u, v, c in edges:
g.add_edge(u, v, c)
return g
TRACE = [(0, 1, 4), (0, 2, 9), (1, 3, 9), (1, 4, 5), (2, 1, 3), (2, 3, 5), (3, 5, 6), (4, 5, 11), (4, 3, 6)]
CLRS = [(0, 1, 16), (0, 2, 13), (1, 3, 12), (2, 1, 4), (2, 4, 14), (3, 2, 9), (3, 5, 20), (4, 3, 7), (4, 5, 4)]
if __name__ == "__main__":
assert build(6, TRACE).max_flow(0, 5) == 11
assert build(6, CLRS).max_flow(0, 5) == 23
assert build(4, [(0, 1, 5), (2, 3, 5)]).max_flow(0, 3) == 0
assert build(3, [(0, 1, 2), (0, 1, 2), (1, 2, 3)]).max_flow(0, 2) == 3
assert build(3, [(0, 1, 5), (1, 0, 3), (1, 2, 4)]).max_flow(0, 2) == 4
print("edmonds-karp ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class EdmondsKarp {
final int n;
final List<List<Integer>> adj = new ArrayList<>();
final List<Integer> to = new ArrayList<>();
final List<Long> cap = new ArrayList<>();
EdmondsKarp(int n) {
this.n = n;
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
}
void addEdge(int u, int v, long c) {
adj.get(u).add(to.size()); to.add(v); cap.add(c);
adj.get(v).add(to.size()); to.add(u); cap.add(0L);
}
long maxFlow(int s, int t) {
long flow = 0;
while (true) {
int[] parEdge = new int[n];
Arrays.fill(parEdge, -1);
parEdge[s] = -2;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty() && parEdge[t] == -1) {
int u = q.poll();
for (int e : adj.get(u)) {
int v = to.get(e);
if (parEdge[v] == -1 && cap.get(e) > 0) { parEdge[v] = e; q.add(v); }
}
}
if (parEdge[t] == -1) return flow;
long b = Long.MAX_VALUE;
for (int v = t; v != s; v = to.get(parEdge[v] ^ 1)) b = Math.min(b, cap.get(parEdge[v]));
for (int v = t; v != s; v = to.get(parEdge[v] ^ 1)) {
int e = parEdge[v];
cap.set(e, cap.get(e) - b);
cap.set(e ^ 1, cap.get(e ^ 1) + b);
}
flow += b;
}
}
static long run(int n, int[][] edges) {
EdmondsKarp g = new EdmondsKarp(n);
for (int[] e : edges) g.addEdge(e[0], e[1], e[2]);
return g.maxFlow(0, n - 1);
}
public static void main(String[] args) {
int[][] trace = {{0, 1, 4}, {0, 2, 9}, {1, 3, 9}, {1, 4, 5}, {2, 1, 3}, {2, 3, 5}, {3, 5, 6}, {4, 5, 11}, {4, 3, 6}};
int[][] clrs = {{0, 1, 16}, {0, 2, 13}, {1, 3, 12}, {2, 1, 4}, {2, 4, 14}, {3, 2, 9}, {3, 5, 20}, {4, 3, 7}, {4, 5, 4}};
if (run(6, trace) != 11) throw new AssertionError("trace");
if (run(6, clrs) != 23) throw new AssertionError("clrs");
if (run(4, new int[][]{{0, 1, 5}, {2, 3, 5}}) != 0) throw new AssertionError("disconnected");
if (run(3, new int[][]{{0, 1, 2}, {0, 1, 2}, {1, 2, 3}}) != 3) throw new AssertionError("parallel");
if (run(3, new int[][]{{0, 1, 5}, {1, 0, 3}, {1, 2, 4}}) != 4) throw new AssertionError("antiparallel");
System.out.println("edmonds-karp ok");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>
struct EdmondsKarp {
int n;
std::vector<std::vector<int>> adj;
std::vector<int> to;
std::vector<long long> cap;
explicit EdmondsKarp(int n) : n(n), adj(n) {}
void addEdge(int u, int v, long long c) {
adj[u].push_back((int)to.size()); to.push_back(v); cap.push_back(c);
adj[v].push_back((int)to.size()); to.push_back(u); cap.push_back(0);
}
long long maxFlow(int s, int t) {
long long flow = 0;
while (true) {
std::vector<int> parEdge(n, -1);
parEdge[s] = -2;
std::queue<int> q;
q.push(s);
while (!q.empty() && parEdge[t] == -1) {
int u = q.front(); q.pop();
for (int e : adj[u]) {
int v = to[e];
if (parEdge[v] == -1 && cap[e] > 0) { parEdge[v] = e; q.push(v); }
}
}
if (parEdge[t] == -1) return flow;
long long b = std::numeric_limits<long long>::max();
for (int v = t; v != s; v = to[parEdge[v] ^ 1]) b = std::min(b, cap[parEdge[v]]);
for (int v = t; v != s; v = to[parEdge[v] ^ 1]) {
cap[parEdge[v]] -= b;
cap[parEdge[v] ^ 1] += b;
}
flow += b;
}
}
};
long long run(int n, const std::vector<std::vector<int>>& edges) {
EdmondsKarp g(n);
for (const auto& e : edges) g.addEdge(e[0], e[1], e[2]);
return g.maxFlow(0, n - 1);
}
int main() {
std::vector<std::vector<int>> trace = {{0, 1, 4}, {0, 2, 9}, {1, 3, 9}, {1, 4, 5}, {2, 1, 3}, {2, 3, 5}, {3, 5, 6}, {4, 5, 11}, {4, 3, 6}};
std::vector<std::vector<int>> clrs = {{0, 1, 16}, {0, 2, 13}, {1, 3, 12}, {2, 1, 4}, {2, 4, 14}, {3, 2, 9}, {3, 5, 20}, {4, 3, 7}, {4, 5, 4}};
assert(run(6, trace) == 11);
assert(run(6, clrs) == 23);
assert(run(4, {{0, 1, 5}, {2, 3, 5}}) == 0);
assert(run(3, {{0, 1, 2}, {0, 1, 2}, {1, 2, 3}}) == 3);
assert(run(3, {{0, 1, 5}, {1, 0, 3}, {1, 2, 4}}) == 4);
std::cout << "edmonds-karp ok\n";
}
class EdmondsKarp {
readonly n: number;
readonly adj: number[][];
readonly to: number[] = [];
readonly cap: number[] = [];
constructor(n: number) {
this.n = n;
this.adj = Array.from({ length: n }, () => []);
}
addEdge(u: number, v: number, c: number): void {
this.adj[u].push(this.to.length); this.to.push(v); this.cap.push(c);
this.adj[v].push(this.to.length); this.to.push(u); this.cap.push(0);
}
maxFlow(s: number, t: number): number {
let flow = 0;
while (true) {
const parEdge: number[] = new Array(this.n).fill(-1);
parEdge[s] = -2;
const q: number[] = [s];
for (let h = 0; h < q.length && parEdge[t] === -1; h++) {
const u = q[h];
for (const e of this.adj[u]) {
const v = this.to[e];
if (parEdge[v] === -1 && this.cap[e] > 0) { parEdge[v] = e; q.push(v); }
}
}
if (parEdge[t] === -1) return flow;
let b = Infinity;
for (let v = t; v !== s; v = this.to[parEdge[v] ^ 1]) b = Math.min(b, this.cap[parEdge[v]]);
for (let v = t; v !== s; v = this.to[parEdge[v] ^ 1]) {
this.cap[parEdge[v]] -= b;
this.cap[parEdge[v] ^ 1] += b;
}
flow += b;
}
}
}
function run(n: number, edges: number[][]): number {
const g = new EdmondsKarp(n);
for (const [u, v, c] of edges) g.addEdge(u, v, c);
return g.maxFlow(0, n - 1);
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const TRACE = [[0, 1, 4], [0, 2, 9], [1, 3, 9], [1, 4, 5], [2, 1, 3], [2, 3, 5], [3, 5, 6], [4, 5, 11], [4, 3, 6]];
const CLRS = [[0, 1, 16], [0, 2, 13], [1, 3, 12], [2, 1, 4], [2, 4, 14], [3, 2, 9], [3, 5, 20], [4, 3, 7], [4, 5, 4]];
check(run(6, TRACE) === 11, "trace");
check(run(6, CLRS) === 23, "clrs");
check(run(4, [[0, 1, 5], [2, 3, 5]]) === 0, "disconnected");
check(run(3, [[0, 1, 2], [0, 1, 2], [1, 2, 3]]) === 3, "parallel");
check(run(3, [[0, 1, 5], [1, 0, 3], [1, 2, 4]]) === 4, "antiparallel");
console.log("edmonds-karp ok");
Dinic with current arcs and min-cut recovery
The DFS is recursive with depth at most (levels strictly increase along it). min_cut_side returns the vertices reachable from in the final residual graph. The last test runs bipartite matching as flow on the 4 + 4 graph from the previous lesson.
import sys
from collections import deque
class Dinic:
def __init__(self, n: int):
sys.setrecursionlimit(max(1000, 2 * n + 100))
self.n = n
self.adj = [[] for _ in range(n)]
self.to: list[int] = []
self.cap: list[int] = []
def add_edge(self, u: int, v: int, c: int) -> int:
self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)
return len(self.to) - 2
def _bfs(self, s: int, t: int) -> bool:
self.level = [-1] * self.n
self.level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in self.adj[u]:
v = self.to[e]
if self.cap[e] > 0 and self.level[v] < 0:
self.level[v] = self.level[u] + 1
q.append(v)
return self.level[t] >= 0
def _dfs(self, u: int, t: int, pushed: int) -> int:
if u == t:
return pushed
while self.it[u] < len(self.adj[u]):
e = self.adj[u][self.it[u]]
v = self.to[e]
if self.cap[e] > 0 and self.level[v] == self.level[u] + 1:
d = self._dfs(v, t, min(pushed, self.cap[e]))
if d > 0:
self.cap[e] -= d
self.cap[e ^ 1] += d
return d
self.it[u] += 1 # current arc: this edge is useless for the phase
return 0
def max_flow(self, s: int, t: int) -> int:
flow = 0
while self._bfs(s, t):
self.it = [0] * self.n
while (f := self._dfs(s, t, float("inf"))) > 0:
flow += f
return flow
def min_cut_side(self, s: int) -> list[int]:
seen = [False] * self.n
seen[s] = True
q = deque([s])
while q:
u = q.popleft()
for e in self.adj[u]:
if self.cap[e] > 0 and not seen[self.to[e]]:
seen[self.to[e]] = True
q.append(self.to[e])
return [v for v in range(self.n) if seen[v]]
TRACE = [(0, 1, 4), (0, 2, 9), (1, 3, 9), (1, 4, 5), (2, 1, 3), (2, 3, 5), (3, 5, 6), (4, 5, 11), (4, 3, 6)]
CLRS = [(0, 1, 16), (0, 2, 13), (1, 3, 12), (2, 1, 4), (2, 4, 14), (3, 2, 9), (3, 5, 20), (4, 3, 7), (4, 5, 4)]
if __name__ == "__main__":
g = Dinic(6)
for u, v, c in TRACE:
g.add_edge(u, v, c)
assert g.max_flow(0, 5) == 11 and g.min_cut_side(0) == [0, 1, 2, 3]
g = Dinic(6)
for u, v, c in CLRS:
g.add_edge(u, v, c)
assert g.max_flow(0, 5) == 23 and g.min_cut_side(0) == [0, 1, 2, 4]
g = Dinic(4)
g.add_edge(0, 1, 5); g.add_edge(2, 3, 5)
assert g.max_flow(0, 3) == 0 and g.min_cut_side(0) == [0, 1]
adj = [[0, 1], [0, 3], [2], [1]] # bipartite matching as flow: s=8, t=9
g = Dinic(10)
for u in range(4):
g.add_edge(8, u, 1)
g.add_edge(4 + u, 9, 1)
for v in adj[u]:
g.add_edge(u, 4 + v, 1)
assert g.max_flow(8, 9) == 4
print("dinic ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Dinic {
final int n;
final List<List<Integer>> adj = new ArrayList<>();
final List<Integer> to = new ArrayList<>();
final List<Long> cap = new ArrayList<>();
int[] level, it;
Dinic(int n) {
this.n = n;
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
}
void addEdge(int u, int v, long c) {
adj.get(u).add(to.size()); to.add(v); cap.add(c);
adj.get(v).add(to.size()); to.add(u); cap.add(0L);
}
boolean bfs(int s, int t) {
level = new int[n];
Arrays.fill(level, -1);
level[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int e : adj.get(u)) {
int v = to.get(e);
if (cap.get(e) > 0 && level[v] < 0) { level[v] = level[u] + 1; q.add(v); }
}
}
return level[t] >= 0;
}
long dfs(int u, int t, long pushed) {
if (u == t) return pushed;
for (; it[u] < adj.get(u).size(); it[u]++) {
int e = adj.get(u).get(it[u]), v = to.get(e);
if (cap.get(e) > 0 && level[v] == level[u] + 1) {
long d = dfs(v, t, Math.min(pushed, cap.get(e)));
if (d > 0) {
cap.set(e, cap.get(e) - d);
cap.set(e ^ 1, cap.get(e ^ 1) + d);
return d;
}
}
}
return 0;
}
long maxFlow(int s, int t) {
long flow = 0;
while (bfs(s, t)) {
it = new int[n];
long f;
while ((f = dfs(s, t, Long.MAX_VALUE)) > 0) flow += f;
}
return flow;
}
List<Integer> minCutSide(int s) {
boolean[] seen = new boolean[n];
seen[s] = true;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int e : adj.get(u)) {
int v = to.get(e);
if (cap.get(e) > 0 && !seen[v]) { seen[v] = true; q.add(v); }
}
}
List<Integer> side = new ArrayList<>();
for (int v = 0; v < n; v++) if (seen[v]) side.add(v);
return side;
}
public static void main(String[] args) {
int[][] trace = {{0, 1, 4}, {0, 2, 9}, {1, 3, 9}, {1, 4, 5}, {2, 1, 3}, {2, 3, 5}, {3, 5, 6}, {4, 5, 11}, {4, 3, 6}};
int[][] clrs = {{0, 1, 16}, {0, 2, 13}, {1, 3, 12}, {2, 1, 4}, {2, 4, 14}, {3, 2, 9}, {3, 5, 20}, {4, 3, 7}, {4, 5, 4}};
Dinic g = new Dinic(6);
for (int[] e : trace) g.addEdge(e[0], e[1], e[2]);
if (g.maxFlow(0, 5) != 11 || !g.minCutSide(0).equals(List.of(0, 1, 2, 3))) throw new AssertionError("trace");
g = new Dinic(6);
for (int[] e : clrs) g.addEdge(e[0], e[1], e[2]);
if (g.maxFlow(0, 5) != 23 || !g.minCutSide(0).equals(List.of(0, 1, 2, 4))) throw new AssertionError("clrs");
g = new Dinic(4);
g.addEdge(0, 1, 5); g.addEdge(2, 3, 5);
if (g.maxFlow(0, 3) != 0 || !g.minCutSide(0).equals(List.of(0, 1))) throw new AssertionError("disconnected");
int[][] adj = {{0, 1}, {0, 3}, {2}, {1}};
g = new Dinic(10);
for (int u = 0; u < 4; u++) {
g.addEdge(8, u, 1);
g.addEdge(4 + u, 9, 1);
for (int v : adj[u]) g.addEdge(u, 4 + v, 1);
}
if (g.maxFlow(8, 9) != 4) throw new AssertionError("matching");
System.out.println("dinic ok");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>
struct Dinic {
int n;
std::vector<std::vector<int>> adj;
std::vector<int> to, level, it;
std::vector<long long> cap;
explicit Dinic(int n) : n(n), adj(n), level(n), it(n) {}
void addEdge(int u, int v, long long c) {
adj[u].push_back((int)to.size()); to.push_back(v); cap.push_back(c);
adj[v].push_back((int)to.size()); to.push_back(u); cap.push_back(0);
}
bool bfs(int s, int t) {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int e : adj[u])
if (cap[e] > 0 && level[to[e]] < 0) { level[to[e]] = level[u] + 1; q.push(to[e]); }
}
return level[t] >= 0;
}
long long dfs(int u, int t, long long pushed) {
if (u == t) return pushed;
for (; it[u] < (int)adj[u].size(); ++it[u]) {
int e = adj[u][it[u]], v = to[e];
if (cap[e] > 0 && level[v] == level[u] + 1) {
long long d = dfs(v, t, std::min(pushed, cap[e]));
if (d > 0) { cap[e] -= d; cap[e ^ 1] += d; return d; }
}
}
return 0;
}
long long maxFlow(int s, int t) {
long long flow = 0;
while (bfs(s, t)) {
std::fill(it.begin(), it.end(), 0);
while (long long f = dfs(s, t, std::numeric_limits<long long>::max())) flow += f;
}
return flow;
}
std::vector<int> minCutSide(int s) const {
std::vector<char> seen(n, 0);
seen[s] = 1;
std::queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int e : adj[u])
if (cap[e] > 0 && !seen[to[e]]) { seen[to[e]] = 1; q.push(to[e]); }
}
std::vector<int> side;
for (int v = 0; v < n; ++v) if (seen[v]) side.push_back(v);
return side;
}
};
int main() {
std::vector<std::vector<int>> trace = {{0, 1, 4}, {0, 2, 9}, {1, 3, 9}, {1, 4, 5}, {2, 1, 3}, {2, 3, 5}, {3, 5, 6}, {4, 5, 11}, {4, 3, 6}};
std::vector<std::vector<int>> clrs = {{0, 1, 16}, {0, 2, 13}, {1, 3, 12}, {2, 1, 4}, {2, 4, 14}, {3, 2, 9}, {3, 5, 20}, {4, 3, 7}, {4, 5, 4}};
Dinic g(6);
for (auto& e : trace) g.addEdge(e[0], e[1], e[2]);
assert(g.maxFlow(0, 5) == 11 && (g.minCutSide(0) == std::vector<int>{0, 1, 2, 3}));
Dinic h(6);
for (auto& e : clrs) h.addEdge(e[0], e[1], e[2]);
assert(h.maxFlow(0, 5) == 23 && (h.minCutSide(0) == std::vector<int>{0, 1, 2, 4}));
Dinic d(4);
d.addEdge(0, 1, 5); d.addEdge(2, 3, 5);
assert(d.maxFlow(0, 3) == 0 && (d.minCutSide(0) == std::vector<int>{0, 1}));
std::vector<std::vector<int>> adj = {{0, 1}, {0, 3}, {2}, {1}};
Dinic m(10);
for (int u = 0; u < 4; ++u) {
m.addEdge(8, u, 1);
m.addEdge(4 + u, 9, 1);
for (int v : adj[u]) m.addEdge(u, 4 + v, 1);
}
assert(m.maxFlow(8, 9) == 4);
std::cout << "dinic ok\n";
}
class Dinic {
readonly n: number;
readonly adj: number[][];
readonly to: number[] = [];
readonly cap: number[] = [];
level: number[] = [];
it: number[] = [];
constructor(n: number) {
this.n = n;
this.adj = Array.from({ length: n }, () => []);
}
addEdge(u: number, v: number, c: number): void {
this.adj[u].push(this.to.length); this.to.push(v); this.cap.push(c);
this.adj[v].push(this.to.length); this.to.push(u); this.cap.push(0);
}
private bfs(s: number, t: number): boolean {
this.level = new Array(this.n).fill(-1);
this.level[s] = 0;
const q: number[] = [s];
for (let h = 0; h < q.length; h++) {
const u = q[h];
for (const e of this.adj[u]) {
const v = this.to[e];
if (this.cap[e] > 0 && this.level[v] < 0) { this.level[v] = this.level[u] + 1; q.push(v); }
}
}
return this.level[t] >= 0;
}
private dfs(u: number, t: number, pushed: number): number {
if (u === t) return pushed;
for (; this.it[u] < this.adj[u].length; this.it[u]++) {
const e = this.adj[u][this.it[u]];
const v = this.to[e];
if (this.cap[e] > 0 && this.level[v] === this.level[u] + 1) {
const d = this.dfs(v, t, Math.min(pushed, this.cap[e]));
if (d > 0) {
this.cap[e] -= d;
this.cap[e ^ 1] += d;
return d;
}
}
}
return 0;
}
maxFlow(s: number, t: number): number {
let flow = 0;
while (this.bfs(s, t)) {
this.it = new Array(this.n).fill(0);
let f: number;
while ((f = this.dfs(s, t, Infinity)) > 0) flow += f;
}
return flow;
}
minCutSide(s: number): number[] {
const seen: boolean[] = new Array(this.n).fill(false);
seen[s] = true;
const q: number[] = [s];
for (let h = 0; h < q.length; h++) {
for (const e of this.adj[q[h]]) {
const v = this.to[e];
if (this.cap[e] > 0 && !seen[v]) { seen[v] = true; q.push(v); }
}
}
const side: number[] = [];
for (let v = 0; v < this.n; v++) if (seen[v]) side.push(v);
return side;
}
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const TRACE = [[0, 1, 4], [0, 2, 9], [1, 3, 9], [1, 4, 5], [2, 1, 3], [2, 3, 5], [3, 5, 6], [4, 5, 11], [4, 3, 6]];
const CLRS = [[0, 1, 16], [0, 2, 13], [1, 3, 12], [2, 1, 4], [2, 4, 14], [3, 2, 9], [3, 5, 20], [4, 3, 7], [4, 5, 4]];
let g = new Dinic(6);
for (const [u, v, c] of TRACE) g.addEdge(u, v, c);
check(g.maxFlow(0, 5) === 11 && g.minCutSide(0).join(",") === "0,1,2,3", "trace");
g = new Dinic(6);
for (const [u, v, c] of CLRS) g.addEdge(u, v, c);
check(g.maxFlow(0, 5) === 23 && g.minCutSide(0).join(",") === "0,1,2,4", "clrs");
g = new Dinic(4);
g.addEdge(0, 1, 5); g.addEdge(2, 3, 5);
check(g.maxFlow(0, 3) === 0 && g.minCutSide(0).join(",") === "0,1", "disconnected");
const adj = [[0, 1], [0, 3], [2], [1]];
g = new Dinic(10);
for (let u = 0; u < 4; u++) {
g.addEdge(8, u, 1);
g.addEdge(4 + u, 9, 1);
for (const v of adj[u]) g.addEdge(u, 4 + v, 1);
}
check(g.maxFlow(8, 9) === 4, "matching");
console.log("dinic ok");
Min-cost max-flow: Bellman–Ford once, then Dijkstra with potentials
min_cost_flow(s, t, max_f) pushes up to max_f units (default: as many as possible) and returns (flow, cost). Negative edge costs are allowed as long as there is no negative cycle. Vertices that become unreachable keep their old potential; they can never become reachable again, because augmentations only change edges between reachable vertices.
import heapq
class MinCostFlow:
def __init__(self, n: int):
self.n = n
self.adj = [[] for _ in range(n)]
self.to: list[int] = []
self.cap: list[int] = []
self.cost: list[int] = []
def add_edge(self, u: int, v: int, cap: int, cost: int) -> None:
self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(cap); self.cost.append(cost)
self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0); self.cost.append(-cost)
def min_cost_flow(self, s: int, t: int, max_f: float = float("inf")) -> tuple[int, int]:
INF = float("inf")
n = self.n
h = [INF] * n # potentials: Bellman-Ford distances
h[s] = 0
for _ in range(n - 1):
changed = False
for u in range(n):
if h[u] == INF:
continue
for e in self.adj[u]:
if self.cap[e] > 0 and h[u] + self.cost[e] < h[self.to[e]]:
h[self.to[e]] = h[u] + self.cost[e]
changed = True
if not changed:
break
h = [x if x < INF else 0 for x in h]
flow = cost = 0
while flow < max_f:
dist = [INF] * n
par_edge = [-1] * n
dist[s] = 0
pq = [(0, s)]
while pq: # Dijkstra on reduced costs (all >= 0)
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for e in self.adj[u]:
v = self.to[e]
nd = d + self.cost[e] + h[u] - h[v]
if self.cap[e] > 0 and nd < dist[v]:
dist[v] = nd
par_edge[v] = e
heapq.heappush(pq, (nd, v))
if dist[t] == INF:
break
for v in range(n):
if dist[v] < INF:
h[v] += dist[v]
push, v = max_f - flow, t
while v != s:
push = min(push, self.cap[par_edge[v]])
v = self.to[par_edge[v] ^ 1]
v = t
while v != s:
e = par_edge[v]
self.cap[e] -= push
self.cap[e ^ 1] += push
v = self.to[e ^ 1]
flow += push
cost += push * (h[t] - h[s]) # true cost of the path
return flow, cost
def build(n, edges):
g = MinCostFlow(n)
for e in edges:
g.add_edge(*e)
return g
SMALL = [(0, 1, 4, 1), (0, 2, 2, 5), (1, 2, 2, 1), (1, 3, 2, 6), (2, 3, 4, 1)]
if __name__ == "__main__":
assert build(4, SMALL).min_cost_flow(0, 3) == (6, 32)
assert build(4, SMALL).min_cost_flow(0, 3, 3) == (3, 12)
assert build(3, [(0, 1, 2, 2), (1, 2, 2, -1), (0, 2, 1, 3)]).min_cost_flow(0, 2) == (3, 5)
c = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]] # assignment as flow
g = MinCostFlow(10)
for i in range(4):
g.add_edge(8, i, 1, 0)
g.add_edge(4 + i, 9, 1, 0)
for j in range(4):
g.add_edge(i, 4 + j, 1, c[i][j])
assert g.min_cost_flow(8, 9) == (4, 13)
print("min-cost flow ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class MinCostFlow {
static final long INF = Long.MAX_VALUE / 4;
final int n;
final List<List<Integer>> adj = new ArrayList<>();
final List<Integer> to = new ArrayList<>();
final List<Long> cap = new ArrayList<>(), cost = new ArrayList<>();
MinCostFlow(int n) {
this.n = n;
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
}
void addEdge(int u, int v, long c, long w) {
adj.get(u).add(to.size()); to.add(v); cap.add(c); cost.add(w);
adj.get(v).add(to.size()); to.add(u); cap.add(0L); cost.add(-w);
}
/** Returns {flow, cost}. */
long[] minCostFlow(int s, int t, long maxF) {
long[] h = new long[n];
Arrays.fill(h, INF);
h[s] = 0;
for (int round = 0; round < n - 1; round++) {
boolean changed = false;
for (int u = 0; u < n; u++) {
if (h[u] == INF) continue;
for (int e : adj.get(u)) {
int v = to.get(e);
if (cap.get(e) > 0 && h[u] + cost.get(e) < h[v]) { h[v] = h[u] + cost.get(e); changed = true; }
}
}
if (!changed) break;
}
for (int v = 0; v < n; v++) if (h[v] == INF) h[v] = 0;
long flow = 0, total = 0;
while (flow < maxF) {
long[] dist = new long[n];
int[] parEdge = new int[n];
Arrays.fill(dist, INF);
Arrays.fill(parEdge, -1);
dist[s] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
pq.add(new long[]{0, s});
while (!pq.isEmpty()) {
long[] top = pq.poll();
int u = (int) top[1];
if (top[0] > dist[u]) continue;
for (int e : adj.get(u)) {
int v = to.get(e);
long nd = top[0] + cost.get(e) + h[u] - h[v];
if (cap.get(e) > 0 && nd < dist[v]) { dist[v] = nd; parEdge[v] = e; pq.add(new long[]{nd, v}); }
}
}
if (dist[t] == INF) break;
for (int v = 0; v < n; v++) if (dist[v] < INF) h[v] += dist[v];
long push = maxF - flow;
for (int v = t; v != s; v = to.get(parEdge[v] ^ 1)) push = Math.min(push, cap.get(parEdge[v]));
for (int v = t; v != s; v = to.get(parEdge[v] ^ 1)) {
int e = parEdge[v];
cap.set(e, cap.get(e) - push);
cap.set(e ^ 1, cap.get(e ^ 1) + push);
}
flow += push;
total += push * (h[t] - h[s]);
}
return new long[]{flow, total};
}
static MinCostFlow build(int n, long[][] edges) {
MinCostFlow g = new MinCostFlow(n);
for (long[] e : edges) g.addEdge((int) e[0], (int) e[1], e[2], e[3]);
return g;
}
public static void main(String[] args) {
long[][] small = {{0, 1, 4, 1}, {0, 2, 2, 5}, {1, 2, 2, 1}, {1, 3, 2, 6}, {2, 3, 4, 1}};
if (!Arrays.equals(build(4, small).minCostFlow(0, 3, INF), new long[]{6, 32})) throw new AssertionError("small");
if (!Arrays.equals(build(4, small).minCostFlow(0, 3, 3), new long[]{3, 12})) throw new AssertionError("limited");
long[][] neg = {{0, 1, 2, 2}, {1, 2, 2, -1}, {0, 2, 1, 3}};
if (!Arrays.equals(build(3, neg).minCostFlow(0, 2, INF), new long[]{3, 5})) throw new AssertionError("negative");
long[][] c = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}};
MinCostFlow g = new MinCostFlow(10);
for (int i = 0; i < 4; i++) {
g.addEdge(8, i, 1, 0);
g.addEdge(4 + i, 9, 1, 0);
for (int j = 0; j < 4; j++) g.addEdge(i, 4 + j, 1, c[i][j]);
}
if (!Arrays.equals(g.minCostFlow(8, 9, INF), new long[]{4, 13})) throw new AssertionError("assignment");
System.out.println("min-cost flow ok");
}
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct MinCostFlow {
static constexpr long long INF = std::numeric_limits<long long>::max() / 4;
int n;
std::vector<std::vector<int>> adj;
std::vector<int> to;
std::vector<long long> cap, cost;
explicit MinCostFlow(int n) : n(n), adj(n) {}
void addEdge(int u, int v, long long c, long long w) {
adj[u].push_back((int)to.size()); to.push_back(v); cap.push_back(c); cost.push_back(w);
adj[v].push_back((int)to.size()); to.push_back(u); cap.push_back(0); cost.push_back(-w);
}
std::pair<long long, long long> minCostFlow(int s, int t, long long maxF = INF) {
std::vector<long long> h(n, INF);
h[s] = 0;
for (int round = 0; round < n - 1; ++round) {
bool changed = false;
for (int u = 0; u < n; ++u) {
if (h[u] == INF) continue;
for (int e : adj[u])
if (cap[e] > 0 && h[u] + cost[e] < h[to[e]]) { h[to[e]] = h[u] + cost[e]; changed = true; }
}
if (!changed) break;
}
for (auto& x : h) if (x == INF) x = 0;
long long flow = 0, total = 0;
using Item = std::pair<long long, int>;
while (flow < maxF) {
std::vector<long long> dist(n, INF);
std::vector<int> parEdge(n, -1);
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (int e : adj[u]) {
int v = to[e];
long long nd = d + cost[e] + h[u] - h[v];
if (cap[e] > 0 && nd < dist[v]) { dist[v] = nd; parEdge[v] = e; pq.push({nd, v}); }
}
}
if (dist[t] == INF) break;
for (int v = 0; v < n; ++v) if (dist[v] < INF) h[v] += dist[v];
long long push = maxF - flow;
for (int v = t; v != s; v = to[parEdge[v] ^ 1]) push = std::min(push, cap[parEdge[v]]);
for (int v = t; v != s; v = to[parEdge[v] ^ 1]) { cap[parEdge[v]] -= push; cap[parEdge[v] ^ 1] += push; }
flow += push;
total += push * (h[t] - h[s]);
}
return {flow, total};
}
};
MinCostFlow build(int n, const std::vector<std::vector<long long>>& edges) {
MinCostFlow g(n);
for (const auto& e : edges) g.addEdge((int)e[0], (int)e[1], e[2], e[3]);
return g;
}
int main() {
std::vector<std::vector<long long>> small = {{0, 1, 4, 1}, {0, 2, 2, 5}, {1, 2, 2, 1}, {1, 3, 2, 6}, {2, 3, 4, 1}};
assert(build(4, small).minCostFlow(0, 3) == std::make_pair(6LL, 32LL));
assert(build(4, small).minCostFlow(0, 3, 3) == std::make_pair(3LL, 12LL));
assert(build(3, {{0, 1, 2, 2}, {1, 2, 2, -1}, {0, 2, 1, 3}}).minCostFlow(0, 2) == std::make_pair(3LL, 5LL));
std::vector<std::vector<long long>> c = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}};
MinCostFlow g(10);
for (int i = 0; i < 4; ++i) {
g.addEdge(8, i, 1, 0);
g.addEdge(4 + i, 9, 1, 0);
for (int j = 0; j < 4; ++j) g.addEdge(i, 4 + j, 1, c[i][j]);
}
assert(g.minCostFlow(8, 9) == std::make_pair(4LL, 13LL));
std::cout << "min-cost flow ok\n";
}
// A small binary heap of [key, vertex] pairs for Dijkstra.
class MinHeap {
private a: [number, number][] = [];
get size(): number { return this.a.length; }
push(x: [number, number]): void {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p][0] <= a[i][0]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop(): [number, number] {
const a = this.a;
const top = a[0];
const last = a.pop()!;
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l][0] < a[m][0]) m = l;
if (r < a.length && a[r][0] < a[m][0]) m = r;
if (m === i) break;
[a[m], a[i]] = [a[i], a[m]];
i = m;
}
}
return top;
}
}
class MinCostFlow {
readonly n: number;
readonly adj: number[][];
readonly to: number[] = [];
readonly cap: number[] = [];
readonly cost: number[] = [];
constructor(n: number) {
this.n = n;
this.adj = Array.from({ length: n }, () => []);
}
addEdge(u: number, v: number, c: number, w: number): void {
this.adj[u].push(this.to.length); this.to.push(v); this.cap.push(c); this.cost.push(w);
this.adj[v].push(this.to.length); this.to.push(u); this.cap.push(0); this.cost.push(-w);
}
minCostFlow(s: number, t: number, maxF: number = Infinity): [number, number] {
const n = this.n;
let h: number[] = new Array(n).fill(Infinity);
h[s] = 0;
for (let round = 0; round < n - 1; round++) {
let changed = false;
for (let u = 0; u < n; u++) {
if (h[u] === Infinity) continue;
for (const e of this.adj[u]) {
const v = this.to[e];
if (this.cap[e] > 0 && h[u] + this.cost[e] < h[v]) { h[v] = h[u] + this.cost[e]; changed = true; }
}
}
if (!changed) break;
}
h = h.map((x) => (x === Infinity ? 0 : x));
let flow = 0;
let total = 0;
while (flow < maxF) {
const dist: number[] = new Array(n).fill(Infinity);
const parEdge: number[] = new Array(n).fill(-1);
dist[s] = 0;
const pq = new MinHeap();
pq.push([0, s]);
while (pq.size > 0) {
const [d, u] = pq.pop();
if (d > dist[u]) continue;
for (const e of this.adj[u]) {
const v = this.to[e];
const nd = d + this.cost[e] + h[u] - h[v];
if (this.cap[e] > 0 && nd < dist[v]) { dist[v] = nd; parEdge[v] = e; pq.push([nd, v]); }
}
}
if (dist[t] === Infinity) break;
for (let v = 0; v < n; v++) if (dist[v] < Infinity) h[v] += dist[v];
let push = maxF - flow;
for (let v = t; v !== s; v = this.to[parEdge[v] ^ 1]) push = Math.min(push, this.cap[parEdge[v]]);
for (let v = t; v !== s; v = this.to[parEdge[v] ^ 1]) {
this.cap[parEdge[v]] -= push;
this.cap[parEdge[v] ^ 1] += push;
}
flow += push;
total += push * (h[t] - h[s]);
}
return [flow, total];
}
}
function build(n: number, edges: number[][]): MinCostFlow {
const g = new MinCostFlow(n);
for (const [u, v, c, w] of edges) g.addEdge(u, v, c, w);
return g;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const SMALL = [[0, 1, 4, 1], [0, 2, 2, 5], [1, 2, 2, 1], [1, 3, 2, 6], [2, 3, 4, 1]];
check(build(4, SMALL).minCostFlow(0, 3).join(",") === "6,32", "small");
check(build(4, SMALL).minCostFlow(0, 3, 3).join(",") === "3,12", "limited");
check(build(3, [[0, 1, 2, 2], [1, 2, 2, -1], [0, 2, 1, 3]]).minCostFlow(0, 2).join(",") === "3,5", "negative");
const C = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]];
const g = new MinCostFlow(10);
for (let i = 0; i < 4; i++) {
g.addEdge(8, i, 1, 0);
g.addEdge(4 + i, 9, 1, 0);
for (let j = 0; j < 4; j++) g.addEdge(i, 4 + j, 1, C[i][j]);
}
check(g.minCostFlow(8, 9).join(",") === "4,13", "assignment");
console.log("min-cost flow ok");
Variant: feasibility with lower bounds
from collections import deque
def max_flow(n, edges, s, t):
"""Edmonds-Karp on an edge list; returns (flow, residual capacities, adjacency, to)."""
adj, to, cap = [[] for _ in range(n)], [], []
for u, v, c in edges:
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
flow = 0
while True:
par = [-1] * n
par[s] = -2
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
if par[t] == -1:
return flow, cap
b, v = float("inf"), t
while v != s:
b = min(b, cap[par[v]]); v = to[par[v] ^ 1]
v = t
while v != s:
cap[par[v]] -= b; cap[par[v] ^ 1] += b; v = to[par[v] ^ 1]
flow += b
def feasible_with_lower_bounds(n, edges, s, t):
"""edges: (u, v, low, high). Is there an s-t flow (any value) meeting every bound?"""
excess = [0] * n
reduced = []
for u, v, lo, hi in edges:
assert 0 <= lo <= hi
reduced.append((u, v, hi - lo))
excess[v] += lo
excess[u] -= lo
big = sum(hi for *_, hi in edges) + 1
reduced.append((t, s, big)) # let flow circulate back to s
S, T = n, n + 1
need = 0
for v in range(n):
if excess[v] > 0:
reduced.append((S, v, excess[v])); need += excess[v]
elif excess[v] < 0:
reduced.append((v, T, -excess[v]))
f, _ = max_flow(n + 2, reduced, S, T)
return f == need
# s=0, a=1, b=2, t=3
ok = [(0, 1, 1, 3), (0, 2, 0, 2), (1, 2, 2, 2), (1, 3, 0, 1), (2, 3, 2, 4)]
assert feasible_with_lower_bounds(4, ok, 0, 3)
bad = [(0, 1, 1, 3), (0, 2, 0, 2), (1, 2, 4, 4), (1, 3, 0, 1), (2, 3, 2, 4)] # a must forward 4 but receives at most 3
assert not feasible_with_lower_bounds(4, bad, 0, 3)
print("lower bounds ok")
Variant: project selection
from collections import deque
from itertools import combinations
def dinic_min_cut(n, edges, s, t):
adj, to, cap = [[] for _ in range(n)], [], []
for u, v, c in edges:
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
flow = 0
while True:
lvl = [-1] * n
lvl[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and lvl[to[e]] < 0:
lvl[to[e]] = lvl[u] + 1
q.append(to[e])
if lvl[t] < 0:
return flow, [v for v in range(n) if lvl[v] >= 0] # reachable set = S side
it = [0] * n
def dfs(u, f):
if u == t:
return f
while it[u] < len(adj[u]):
e = adj[u][it[u]]
if cap[e] > 0 and lvl[to[e]] == lvl[u] + 1:
d = dfs(to[e], min(f, cap[e]))
if d:
cap[e] -= d; cap[e ^ 1] += d
return d
it[u] += 1
return 0
while (f := dfs(s, float("inf"))):
flow += f
def project_selection(profit: list[int], requires: list[tuple[int, int]]) -> tuple[int, list[int]]:
n = len(profit)
s, t = n, n + 1
inf = sum(abs(p) for p in profit) + 1
edges = [(s, i, p) for i, p in enumerate(profit) if p > 0]
edges += [(i, t, -p) for i, p in enumerate(profit) if p < 0]
edges += [(i, j, inf) for i, j in requires] # choosing i forces j
cut, side = dinic_min_cut(n + 2, edges, s, t)
return sum(p for p in profit if p > 0) - cut, [i for i in side if i < n]
profit = [12, 6, -4, -5, -7] # app, analytics, API, database, pipeline
requires = [(0, 2), (0, 3), (1, 3), (1, 4)]
best, chosen = project_selection(profit, requires)
assert (best, chosen) == (3, [0, 2, 3])
def brute(profit, requires):
n, best = len(profit), 0
for k in range(n + 1):
for sub in combinations(range(n), k):
ss = set(sub)
if all(j in ss for i, j in requires if i in ss):
best = max(best, sum(profit[i] for i in ss))
return best
import random
random.seed(1)
for _ in range(200):
n = random.randint(1, 7)
pr = [random.randint(-9, 9) for _ in range(n)]
rq = [(i, j) for i in range(n) for j in range(n) if i != j and random.random() < 0.2]
assert project_selection(pr, rq)[0] == brute(pr, rq)
print("project selection ok")
Variant: baseball elimination with a certificate
from collections import deque
def max_flow_side(n, edges, s, t):
adj, to, cap = [[] for _ in range(n)], [], []
for u, v, c in edges:
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
flow = 0
while True:
par = [-1] * n
par[s] = -2
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
if par[t] == -1:
return flow, {v for v in range(n) if par[v] != -1}
b, v = float("inf"), t
while v != s:
b = min(b, cap[par[v]]); v = to[par[v] ^ 1]
v = t
while v != s:
cap[par[v]] -= b; cap[par[v] ^ 1] += b; v = to[par[v] ^ 1]
flow += b
def eliminated(x: int, wins: list[int], left: list[int], games: list[list[int]]):
"""Return None if team x can still finish first (ties allowed), else a certificate set R."""
n = len(wins)
best_x = wins[x] + left[x]
trivial = [i for i in range(n) if wins[i] > best_x]
if trivial:
return trivial
others = [i for i in range(n) if i != x]
pairs = [(i, j) for a, i in enumerate(others) for j in others[a + 1:] if games[i][j] > 0]
s, t = 0, 1
gid = {p: 2 + k for k, p in enumerate(pairs)}
tid = {i: 2 + len(pairs) + k for k, i in enumerate(others)}
inf = sum(left) + 1
edges = []
for (i, j), g in gid.items():
edges += [(s, g, games[i][j]), (g, tid[i], inf), (g, tid[j], inf)]
for i in others:
edges.append((tid[i], t, best_x - wins[i]))
flow, side = max_flow_side(2 + len(pairs) + len(others), edges, s, t)
if flow == sum(games[i][j] for i, j in pairs):
return None
return [i for i in others if tid[i] in side]
teams = ["Atlanta", "Philadelphia", "New York", "Montreal"]
wins = [83, 80, 78, 77]
left = [8, 3, 6, 3]
games = [[0, 1, 6, 1], [1, 0, 0, 2], [6, 0, 0, 0], [1, 2, 0, 0]]
assert eliminated(0, wins, left, games) is None
assert [teams[i] for i in eliminated(1, wins, left, games)] == ["Atlanta", "New York"]
assert eliminated(2, wins, left, games) is None
assert [teams[i] for i in eliminated(3, wins, left, games)] == ["Atlanta"]
print("baseball ok")
Real-world uses
Transport and logistics. The problem that started the field — how much can a rail network carry, and where is its bottleneck — is still how freight and supply-chain planners use flow, usually as min-cost flow or its linear-programming generalisation (multi-commodity flow, which is no longer solvable by these combinatorial algorithms in general and is handed to LP solvers). The transportation problem of Hitchcock (1941) and Kantorovich is min-cost flow on a bipartite graph.
Airline scheduling. Fleet assignment and aircraft routing are flow problems on time-space networks (nodes are airport-time pairs, arcs are flights and ground waits); the textbook version is Kleinberg & Tardos §7.9. Production systems add many side constraints and use integer programming with network-flow substructure; treat flow as the core idea rather than the whole solver.
Cluster scheduling. Quincy (Isard et al., SOSP 2009) scheduled Dryad jobs on Microsoft clusters by solving a min-cost flow where tasks flow to machines, with costs encoding data locality and fairness; Firmament (Gog et al., OSDI 2016) made min-cost-flow scheduling fast enough for sub-second decisions on large clusters, and was integrated experimentally with Kubernetes under the name Poseidon. The default Kubernetes scheduler does not use flow: it filters and scores nodes one pod at a time (see Kubernetes architecture internals). The flow approach optimises placement globally across all pending tasks at once, at the cost of a bigger solve per decision.
Computer vision. Graph-cut segmentation (Boykov & Jolly 2001; "GrabCut", Rother, Kolmogorov & Blake 2004) and stereo correspondence by α-expansion are min-cut computations on grid graphs with millions of vertices, solved with the Boykov–Kolmogorov algorithm. This was the dominant approach to interactive segmentation before deep learning, and graph cuts remain a standard post-processing and teaching tool.
Network reliability and routing. The minimum number of links whose failure disconnects two data centres is a min cut (Menger); the maximum number of link-disjoint paths available for protection routing is a max flow. Traffic engineering in backbone networks is a multi-commodity flow problem; see the network layer and BGP for the routing side. Load spreading across backends (load-balancing algorithms) is a much simpler online cousin.
Data placement. Assigning shards or replicas to machines under per-machine capacity limits is a bipartite b-matching, and "rebalance while moving as little data as possible" is a min-cost flow with the current placement as zero-cost edges. This is a modelling pattern, not a claim about any particular database's rebalancer; see consistent hashing for the approach most systems actually use, which trades optimality for zero coordination.
Optimal transport and sports. The earth mover's distance between two histograms — used in image retrieval and as a loss in machine learning — is a min-cost flow (transportation) problem; the Python Optimal Transport library's exact emd solver is a network simplex. Baseball elimination (Schwartz 1966) is the playful classic and a staple of algorithms courses.
Pitfalls & edge cases
- Forgetting reverse edges. Without backward residual edges, augmenting is just greedy path-packing and returns a non-maximum flow (the diamond example).
- Storing the reverse edge's index wrongly. With the paired-array layout,
e ^ 1is the partner only if edges are added two at a time starting at index 0. Mixing in single additions breaks it silently. - Undirected edges. Add each as two directed edges of capacity — or, more economically, one pair whose "reverse" also starts at capacity . Do not model an undirected edge as a single directed edge.
- Overflow. Sum of capacities can exceed 32 bits; "infinite" capacities must be large but not so large that adding a few of them overflows. Use 64-bit and an INF like or the sum of finite capacities + 1.
- Using
s == t. Max flow is undefined/infinite; guard it. - DFS recursion depth in Dinic. Bounded by the level of , at most — fine in C++ for , but Python needs a raised limit or an iterative DFS.
- Resetting current arcs at the wrong time. Reset
itonce per phase (after each BFS), not per DFS call. Resetting per DFS loses the blocking-flow bound; never resetting gives wrong answers. - Min cut from the wrong side. The cut is reachable-from- in the residual graph after max flow, not in the original graph, and cut edges are original edges from to — not reverse edges.
- Min-cost flow with negative cycles. SSP assumes none in the initial graph. If there are, cancel them first (cycle canceling) or saturate negative edges up front and fix the imbalance with lower-bound tricks.
- Dijkstra without potentials on residual graphs with negative backward edges — gives wrong shortest paths. Bellman–Ford/SPFA every iteration is correct but slower; potentials are the fix.
- SPFA worst cases. SPFA (queue-based Bellman–Ford) is fast on average but exponential-ish adversarial inputs exist in contests; use it only for the initial potentials or on trusted inputs.
- Pseudo-polynomial assumptions. SSP's running time scales with the flow value . If capacities are huge, use capacity scaling or a cost-scaling algorithm.
- Modelling vertex capacities on and . Splitting or caps total flow; usually you want to split only internal vertices.
Variations
- Global min cut (no fixed , ; undirected): Stoer–Wagner deterministic, or Karger's randomised contraction. Running max flows also works (Gomory–Hu trees give all-pairs min cuts with max-flow computations).
- Multi-commodity flow: several source–sink pairs sharing capacities. Fractional version is an LP; integral version is NP-hard. Max-flow min-cut no longer holds exactly.
- Flows over time / dynamic flows: edges have transit times; "quickest transshipment" and evacuation planning.
- Generalised flows (gains/losses): flow is multiplied by a factor along each edge (currency exchange, leaky pipes).
- Circulation and min-cost circulation: no source/sink; demands on vertices; the unifying formulation for lower bounds and many scheduling problems.
- Maximum closure, densest subgraph (Goldberg 1984, by binary search on density + min cut), selection problems — all min cuts.
- Assignment special case: Hungarian (previous lesson) or auction algorithms beat general min-cost flow on dense square instances.
- Parametric max flow (Gallo, Grigoriadis & Tarjan 1989): capacities depending monotonically on a parameter, all breakpoints in the time of one push-relabel run.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Download Speed (CSES 1694) — Computers connected by directed links with speeds; find the maximum transfer rate from computer 1 to computer n. Teaches a plain max flow with 64-bit capacities.
Hint
Dinic or Edmonds–Karp (, ). Parallel links must each get their own edge pair.
Solution
from collections import deque
from itertools import combinations
def download_speed(n: int, links: list[tuple[int, int, int]]) -> int:
adj, to, cap = [[] for _ in range(n + 1)], [], []
for a, b, c in links:
adj[a].append(len(to)); to.append(b); cap.append(c)
adj[b].append(len(to)); to.append(a); cap.append(0)
s, t, flow = 1, n, 0
while True:
lvl = [-1] * (n + 1)
lvl[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and lvl[to[e]] < 0:
lvl[to[e]] = lvl[u] + 1
q.append(to[e])
if lvl[t] < 0:
return flow
it = [0] * (n + 1)
def dfs(u, f):
if u == t:
return f
while it[u] < len(adj[u]):
e = adj[u][it[u]]
if cap[e] > 0 and lvl[to[e]] == lvl[u] + 1:
d = dfs(to[e], min(f, cap[e]))
if d:
cap[e] -= d; cap[e ^ 1] += d
return d
it[u] += 1
return 0
while (f := dfs(s, float("inf"))):
flow += f
def brute_cut(n, links):
best = None
others = list(range(2, n))
for k in range(len(others) + 1):
for sub in combinations(others, k):
S = {1, *sub}
c = sum(w for a, b, w in links if a in S and b not in S)
best = c if best is None else min(best, c)
return best
sample = [(1, 2, 3), (2, 4, 2), (1, 3, 4), (3, 4, 5), (4, 1, 3)]
assert download_speed(4, sample) == brute_cut(4, sample) == 6
print("1694 ok")
worst case; a few milliseconds at these limits in C++, fine in Python too.
2. Police Chase (CSES 1695) — Close the fewest two-way streets so that there is no route from crossing 1 to crossing n, and list them. Teaches min-cut recovery on an undirected graph.
Hint
Each street is capacity 1 in both directions. After max flow, BFS from 1 in the residual graph; print original streets with exactly one endpoint reachable.
Solution
from collections import deque
from itertools import combinations
def police_chase(n: int, streets: list[tuple[int, int]]) -> list[tuple[int, int]]:
adj, to, cap = [[] for _ in range(n + 1)], [], []
for a, b in streets: # undirected: one pair, capacity 1 each way
adj[a].append(len(to)); to.append(b); cap.append(1)
adj[b].append(len(to)); to.append(a); cap.append(1)
def bfs_parents():
par = [-1] * (n + 1)
par[1] = -2
q = deque([1])
while q:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
return par
while (par := bfs_parents())[n] != -1: # unit bottleneck each time
v = n
while v != 1:
cap[par[v]] -= 1; cap[par[v] ^ 1] += 1; v = to[par[v] ^ 1]
reach = {v for v in range(1, n + 1) if par[v] != -1}
return [(a, b) for a, b in streets if (a in reach) != (b in reach)]
def brute(n, streets):
for k in range(len(streets) + 1):
for closed in combinations(range(len(streets)), k):
open_ = [streets[i] for i in range(len(streets)) if i not in closed]
seen, stack = {1}, [1]
while stack:
u = stack.pop()
for a, b in open_:
for x, y in ((a, b), (b, a)):
if x == u and y not in seen:
seen.add(y); stack.append(y)
if n not in seen:
return k
st = [(1, 2), (1, 3), (2, 3), (3, 4), (1, 4)]
cut = police_chase(4, st)
assert len(cut) == brute(4, st) == 2
import random
random.seed(2)
for _ in range(100):
n = random.randint(2, 6)
es = list({tuple(sorted(random.sample(range(1, n + 1), 2))) for _ in range(random.randint(1, 8))})
assert len(police_chase(n, es)) == brute(n, es)
print("1695 ok")
here since the flow value is at most the degree of vertex 1.
3. School Dance (CSES 1696) — Maximum pairing of boys and girls who are willing to dance together. Teaches bipartite matching as unit-capacity flow.
Hint
boy (1), boy girl (1), girl (1). Pairs are the boy→girl edges with zero residual capacity.
4. Distinct Routes (CSES 1711) — Find the maximum number of days a game can be played if each day is a route from room 1 to room n and no one-way teleporter is used twice overall, and print the routes. Teaches edge-disjoint paths and flow decomposition.
Hint
Unit capacities, max flow from 1 to n. Then repeatedly walk from 1 following original edges that carry flow, consuming each edge as you use it.
Solution
from collections import deque
def distinct_routes(n: int, tele: list[tuple[int, int]]) -> list[list[int]]:
adj, to, cap = [[] for _ in range(n + 1)], [], []
for a, b in tele:
adj[a].append(len(to)); to.append(b); cap.append(1)
adj[b].append(len(to)); to.append(a); cap.append(0)
while True:
par = [-1] * (n + 1)
par[1] = -2
q = deque([1])
while q:
u = q.popleft()
for e in adj[u]:
if par[to[e]] == -1 and cap[e] > 0:
par[to[e]] = e
q.append(to[e])
if par[n] == -1:
break
v = n
while v != 1:
cap[par[v]] -= 1; cap[par[v] ^ 1] += 1; v = to[par[v] ^ 1]
used = [e % 2 == 0 and cap[e] == 0 for e in range(len(to))] # forward edges carrying flow
routes = []
while True:
path, u = [1], 1
while u != n:
nxt = next((e for e in adj[u] if used[e]), None)
if nxt is None:
break
used[nxt] = False
u = to[nxt]
path.append(u)
if u != n:
break
routes.append(path)
return routes
r = distinct_routes(6, [(1, 2), (1, 3), (2, 6), (3, 4), (3, 2), (4, 6), (2, 5), (5, 6)])
assert len(r) == 2 and all(p[0] == 1 and p[-1] == 6 for p in r)
edges_used = [(p[i], p[i + 1]) for p in r for i in range(len(p) - 1)]
assert len(edges_used) == len(set(edges_used))
print("1711 ok")
for the flow (value ≤ out-degree of 1) plus decomposition. Cycles in the flow are harmless here: they are simply never followed to n.
5. Maxflow (AtCoder Library Practice Contest D) — Place as many 1×2 dominoes as possible on a grid with blocked cells and print the tiling. Teaches matching on a grid via the checkerboard bipartition.
Hint
Black cells even on the left, white on the right, edges between adjacent free cells. Max flow, then read off which edges carry flow.
6. Fast Maximum Flow (SPOJ FASTFLOW) — Undirected max flow with 5000 vertices and 30 000 edges. Teaches why Dinic (or push-relabel) and a tight implementation matter.
Hint
Undirected edges as one pair with capacity both ways. Dinic with current arcs and flat arrays; 64-bit answer.
7. Delivery Bears (Codeforces 653D) — Each of bears carries the same weight along a path from 1 to n; edge capacities limit total weight. Maximise total delivered. Teaches binary search on the answer with a flow feasibility check.
Hint
For a per-bear weight , edge admits bears. Feasible iff max flow (counting bears) is at least . Binary search over reals (about 100 iterations).
8. Petya and Graph (Codeforces 1082G) — Choose a subgraph to maximise the sum of chosen edge weights minus the sum of chosen vertex weights. Teaches maximum-weight closure.
Hint
Each edge is a project with profit that requires both endpoints; each vertex is a project with cost . Project selection network.
Solution
from collections import deque
from itertools import combinations
def petya_graph(a: list[int], edges: list[tuple[int, int, int]]) -> int:
n, m = len(a), len(edges)
s, t = n + m, n + m + 1
N = n + m + 2
adj, to, cap = [[] for _ in range(N)], [], []
def add(u, v, c):
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
inf = sum(w for *_, w in edges) + 1
for i, (u, v, w) in enumerate(edges):
add(s, n + i, w)
add(n + i, u - 1, inf)
add(n + i, v - 1, inf)
for v in range(n):
add(v, t, a[v])
flow = 0
while True:
lvl = [-1] * N
lvl[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and lvl[to[e]] < 0:
lvl[to[e]] = lvl[u] + 1
q.append(to[e])
if lvl[t] < 0:
break
it = [0] * N
def dfs(u, f):
if u == t:
return f
while it[u] < len(adj[u]):
e = adj[u][it[u]]
if cap[e] > 0 and lvl[to[e]] == lvl[u] + 1:
d = dfs(to[e], min(f, cap[e]))
if d:
cap[e] -= d; cap[e ^ 1] += d
return d
it[u] += 1
return 0
while (f := dfs(s, float("inf"))):
flow += f
return sum(w for *_, w in edges) - flow
def brute(a, edges):
best = 0
for k in range(len(a) + 1):
for vs in combinations(range(1, len(a) + 1), k):
S = set(vs)
best = max(best, sum(w for u, v, w in edges if u in S and v in S) - sum(a[v - 1] for v in S))
return best
ex1 = ([1, 5, 2, 2], [(1, 3, 4), (1, 4, 4), (3, 4, 5), (3, 2, 2), (4, 2, 2)])
ex2 = ([9, 7, 8], [(1, 2, 1), (2, 3, 2), (1, 3, 3)])
assert petya_graph(*ex1) == brute(*ex1) == 8
assert petya_graph(*ex2) == brute(*ex2) == 0
print("1082G ok")
with ; Dinic is fast here in practice.
9. Minimum Moves to Spread Stones Over Grid (LeetCode 2850) — Nine stones on a 3×3 grid; move stones one step at a time so every cell has exactly one, minimising moves. Teaches spotting an assignment / min-cost flow behind a puzzle.
Hint
Each surplus stone must travel to some empty cell, and moves cost Manhattan distance. Min-cost flow from surplus cells to empty cells (or try all permutations — at most 8! here).
Solution
import heapq
from itertools import permutations
def min_moves(grid: list[list[int]]) -> int:
cells = [(r, c) for r in range(3) for c in range(3)]
n = 11 # 9 cells + s (9) + t (10)
s, t = 9, 10
adj, to, cap, cost = [[] for _ in range(n)], [], [], []
def add(u, v, c, w):
adj[u].append(len(to)); to.append(v); cap.append(c); cost.append(w)
adj[v].append(len(to)); to.append(u); cap.append(0); cost.append(-w)
for i, (r, c) in enumerate(cells):
if grid[r][c] > 1:
add(s, i, grid[r][c] - 1, 0)
if grid[r][c] == 0:
add(i, t, 1, 0)
for i, (r1, c1) in enumerate(cells):
for j, (r2, c2) in enumerate(cells):
if grid[r1][c1] > 1 and grid[r2][c2] == 0:
add(i, j, 9, abs(r1 - r2) + abs(c1 - c2))
h, total = [0] * n, 0 # all costs >= 0, so h = 0 is a valid start
while True:
dist, par = [float("inf")] * n, [-1] * n
dist[s] = 0
pq = [(0, s)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for e in adj[u]:
nd = d + cost[e] + h[u] - h[to[e]]
if cap[e] > 0 and nd < dist[to[e]]:
dist[to[e]], par[to[e]] = nd, e
heapq.heappush(pq, (nd, to[e]))
if dist[t] == float("inf"):
return total
for v in range(n):
if dist[v] < float("inf"):
h[v] += dist[v]
v = t
while v != s:
cap[par[v]] -= 1; cap[par[v] ^ 1] += 1; v = to[par[v] ^ 1]
total += h[t] - h[s]
def brute(grid):
src = [(r, c) for r in range(3) for c in range(3) for _ in range(max(0, grid[r][c] - 1))]
dst = [(r, c) for r in range(3) for c in range(3) if grid[r][c] == 0]
return min((sum(abs(a[0] - b[0]) + abs(a[1] - b[1]) for a, b in zip(src, p)) for p in permutations(dst)), default=0)
for g in ([[1, 1, 0], [1, 1, 1], [1, 2, 1]], [[1, 3, 0], [1, 0, 0], [1, 0, 3]], [[1] * 3] * 3):
assert min_moves(g) == brute(g)
assert min_moves([[1, 1, 0], [1, 1, 1], [1, 2, 1]]) == 3
assert min_moves([[1, 3, 0], [1, 0, 0], [1, 0, 3]]) == 4
print("2850 ok")
Each unit is one Dijkstra on 11 vertices; trivially fast. Moving a stone through occupied cells is allowed, which is why Manhattan distance is the exact cost.
10. Task Assignment (CSES 2129) — Assign employees to tasks at minimum total cost and print the pairs. Teaches min-cost flow as an alternative to Hungarian.
Hint
Bipartite network with unit capacities and the given costs; means Dijkstras on edges.
11. MinCostFlow (AtCoder Library Practice Contest E) — Pick cells of a grid with values to maximise the total, with at most picks per row and per column. Teaches maximum-weight b-matching via min-cost flow with negated costs.
Hint
row (cap ), row column (cap 1, cost ), column (cap ). Add a bypass edge with cost 0 (or stop when the next path cost is non-negative) so you never take a harmful unit. Offsetting costs by a large constant avoids negative edges.
12. Binary Tree on Plane (Codeforces 277E) — Connect points into a binary tree with edges pointing downward (parent strictly higher) to minimise total edge length, or report impossibility. Teaches degree-constrained assignment as min-cost flow with real costs.
Hint
Each node needs exactly one parent (except the root) and can have at most two children: child-copy (1), child-copy parent-copy (1, cost = distance, only if the parent is higher), parent-copy (2). Feasible iff flow = .
13. Incorrect Flow (Codeforces 708D) — Given a network whose recorded flow violates capacities and conservation, change values minimally (total absolute change) to make it a valid flow. Teaches min-cost circulation with piecewise-linear costs and lower bounds.
Hint
If : raising the flow costs 1 per unit up to and 2 per unit beyond (the capacity must rise too); lowering costs 1. If : pay up front; lowering down to is then free, lowering further costs 1, raising costs 2. Model the cost pieces as parallel edges and fix conservation imbalances with a super source/sink.
14. Red-Blue Graph (Codeforces 1288F) — Colour some edges of a bipartite graph red or blue (each colour has a price; edges may stay uncoloured) so that every red vertex has strictly more red than blue edges and every blue vertex the reverse, at minimum cost. Teaches min-cost flow with lower bounds.
Hint
Red and blue are flow in opposite directions on each edge. "Strictly more red" is a lower bound of 1 on that vertex's net flow. Apply the lower-bounds construction, then min-cost flow.
Common mistakes & interview follow-ups
"Why do you need backward edges?" Because a greedy path choice can block the optimum; backward edges let later paths cancel earlier flow. Draw the diamond with a cross edge.
"Prove your answer is optimal." Exhibit the min cut: the vertices reachable from in the residual graph. Its capacity equals the flow; weak duality finishes the proof.
"What's the complexity of Ford–Fulkerson?" — pseudo-polynomial; not even guaranteed to terminate with irrational capacities. Edmonds–Karp fixes it with BFS: .
"Max flow with vertex capacities?" Split each vertex into in/out with the vertex capacity on the connecting edge.
"Many sources and sinks?" Super-source and super-sink.
"Undirected graph?" Two directed edges (or one pair with both capacities ). The min cut is then the minimum set of undirected edges separating from .
"What if capacities change online?" Increasing a capacity: continue augmenting from the current flow. Decreasing: if the edge now carries more than its capacity, push the excess back (find paths to return it) — still usually far cheaper than recomputing. Dynamic max flow is an active research area.
"How would you minimise cost too?" Successive shortest paths with Bellman–Ford once and Dijkstra with potentials afterwards; mention negative cycles and pseudo-polynomiality.
"Where is this used in practice?" Image segmentation by graph cuts, cluster scheduling (Quincy, Firmament), transport planning, network reliability (Menger), project selection. Be honest that large production systems often embed flow in LP/ILP solvers.
Common mistakes interviewers watch for: forgetting reverse edges, using DFS and claiming polynomial time, reading the min cut from the original rather than the residual graph, 32-bit overflow, and modelling an undirected edge as one directed edge.
Quick quiz
1. In the Edmonds–Karp trace, why can the fourth augmenting path pass from c to a when the network has no edge c→a?
Answer
Because a→c carries flow (4 units after iteration 1), the residual graph contains the backward edge c→a with capacity 4. Traversing it cancels 2 units of a→c flow.
2. A network has a cut of capacity 17 and you have found a flow of value 17. What can you conclude?
Answer
Both are optimal: by weak duality no flow exceeds 17 and no cut is below 17.
3. How do you find the maximum number of vertex-disjoint paths from to ?
Answer
Split every vertex other than and into with capacity 1, give all original edges capacity 1 (or ), and compute max flow.
4. Why does Dinic need at most phases?
Answer
Each phase saturates a blocking flow in the level graph, after which every remaining - path in the residual graph is strictly longer. The distance from to is at most .
5. In successive shortest paths, why are reduced costs non-negative after updating potentials with Dijkstra distances?
Answer
With equal to shortest-path distances, every residual edge satisfies , i.e. . Edges on the shortest path have , so the reverse edges created by augmentation also have .
Further reading / sources
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed. (2009), chapter 26 "Maximum Flow" (26.2 Ford–Fulkerson and Edmonds–Karp with Lemma 26.7, 26.3 bipartite matching, 26.4–26.5 push-relabel); 4th ed. (2022), chapter 24 "Maximum Flow".
- J. Kleinberg, É. Tardos, Algorithm Design (2005), chapter 7 "Network Flow": §7.1–7.3 Ford–Fulkerson, max-flow min-cut, scaling; §7.5–7.6 matching and disjoint paths; §7.7 circulations with demands and lower bounds; §7.8 survey design; §7.9 airline scheduling; §7.10 image segmentation; §7.11 project selection; §7.12 baseball elimination; §7.13 adding costs.
- R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (1993) — the reference for min-cost flow algorithms and optimality conditions.
- cp-algorithms: Maximum flow — Ford-Fulkerson and Edmonds-Karp, Dinic's algorithm, Push-relabel, Flows with demands, Minimum-cost flow.
- L. R. Ford, D. R. Fulkerson, "Maximal flow through a network", Canadian J. Math. 8, 1956; P. Elias, A. Feinstein, C. E. Shannon, "A note on the maximum flow through a network", IRE Trans. Information Theory 2(4), 1956; A. Schrijver, "On the history of the transportation and maximum flow problems", Mathematical Programming 91, 2002 (the Harris–Ross story).
- J. Edmonds, R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems", JACM 19(2), 1972; E. A. Dinic, "Algorithm for solution of a problem of maximum flow in networks with power estimation", Soviet Math. Doklady 11, 1970; S. Even, R. E. Tarjan, "Network flow and testing graph connectivity", SIAM J. Computing 4(4), 1975.
- A. V. Goldberg, R. E. Tarjan, "A new approach to the maximum-flow problem", JACM 35(4), 1988; J. B. Orlin, "Max flows in O(nm) time, or better", STOC 2013; L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva, "Maximum flow and minimum-cost flow in almost-linear time", FOCS 2022 (arXiv:2203.00671).
- U. Zwick, "The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate", Theoretical Computer Science 148(1), 1995.
- J.-C. Picard, "Maximal closure of a graph and applications to combinatorial problems", Management Science 22(11), 1976; B. L. Schwartz, "Possible winners in partially completed tournaments", SIAM Review 8(3), 1966.
- D. M. Greig, B. T. Porteous, A. H. Seheult, "Exact maximum a posteriori estimation for binary images", J. Royal Statistical Society B 51(2), 1989; Y. Boykov, V. Kolmogorov, "An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision", IEEE TPAMI 26(9), 2004; V. Kolmogorov, R. Zabih, "What energy functions can be minimized via graph cuts?", IEEE TPAMI 26(2), 2004.
- M. Isard et al., "Quincy: fair scheduling for distributed computing clusters", SOSP 2009; I. Gog, M. Schwarzkopf, A. Gleave, R. N. M. Watson, S. Hand, "Firmament: fast, centralized cluster scheduling at scale", OSDI 2016.
Previous lesson: Bipartite Graphs, Matching & the Hungarian Algorithm · Next lesson: 2-SAT, Graph Coloring & Other Classic Graph Problems
Related: Graphs overview (Module 4) · BFS in Depth · Shortest Paths · Connectivity: Bridges, Articulation Points & SCCs · Graph Algorithms in the Real World · Greedy Algorithms · Dynamic Programming · Course home