Network Flow Algorithms Cheat Sheet

Updated 2026-05-19

🧠Study flashcards on this topic110 cards · spaced repetition→

Network flow algorithms solve optimization problems on directed graphs where edges have capacities and we route flow from a source to a sink. They underpin matching, scheduling, routing, and combinatorial optimization across computer science, operations research, and competitive programming.

What This Cheat Sheet Covers

This topic spans 12 focused tables and 142 indexed concepts, 110 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Flow Network FundamentalsTable 2: Max-Flow Min-Cut TheoremTable 3: Ford-Fulkerson MethodTable 4: Edmonds-Karp AlgorithmTable 5: Dinic's AlgorithmTable 6: Push-Relabel FrameworkTable 7: Push-Relabel Variants and HeuristicsTable 8: Minimum-Cost FlowTable 9: Bipartite MatchingTable 10: Flow Decomposition and ExtensionsTable 11: Algorithm Complexity ComparisonTable 12: Implementation Patterns

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

Table 1: Flow Network Fundamentals

Every flow algorithm rests on the same vocabulary, and these are the terms you'll lean on throughout. Capacity and conservation constraints define what a valid flow is; the residual graph and augmenting paths define how you improve one; and the s-t cut sets up the duality that the rest of the cheat sheet exploits. Get comfortable here before reaching for any specific algorithm.

Concept	Example	Description
Flow network	`G=(V,E), s,t∈V, cap:E→ℝ≥0`	Directed graph with source s, sink t, non-negative edge capacities
Flow	`f(u,v) ∈ [0, cap(u,v)]`	Assignment satisfying capacity and conservation constraints
Capacity constraint	`0 ≤ f(u,v) ≤ cap(u,v)`	Flow on each edge cannot exceed its capacity
Flow conservation	`∑f(u,v) = ∑f(v,w) ∀v≠s,t`	Flow in equals flow out at every internal vertex
Value of flow	`\|f\| = ∑f(s,v)`	Total flow leaving source (or entering sink)
Residual graph	`Gf: cf(u,v)=cap(u,v)-f(u,v)`	• Graph of remaining capacities • adds backward edge with capacity f(u,v)
Residual capacity	`cf(u,v) = cap(u,v) - f(u,v)`	• Remaining capacity on forward edge • f(u,v) on backward edge
Augmenting path	`s→a→b→t` in `Gf`	Path from s to t in residual graph with all positive residual capacities
Bottleneck capacity	`Δ = min{cf(e) : e∈P}`	Minimum residual capacity along augmenting path P
s-t cut	`(S,T): s∈S, t∈T, S∪T=V`	• Partition of V • capacity = sum of caps of edges from S to T
Cut capacity	`cap(S,T) = ∑cap(u,v): u∈S,v∈T`	Sum of capacities of forward edges crossing the cut
Minimum cut	`min over all s-t cuts of cap(S,T)`	• Cut with smallest total capacity • equals max flow by theorem
Integral flow theorem	All `cap∈ℤ≥0 ⟹ ∃f∗∈ℤ≥0`	If all capacities are integers, there exists an integer-valued max flow
Skew symmetry	`f(u,v) = -f(v,u)`	Anti-symmetry property of flow on pairs of edges
Parallel edges	`cap[u][v] += c` per edge	• Multiple edges between same pair • handled by summing capacities in adjacency matrix

Table 2: Max-Flow Min-Cut Theorem

The single most important result in the field: the maximum flow you can push equals the cheapest cut you can make separating source from sink. The rows trace why—weak duality bounds flow below any cut, strong duality makes it tight at the optimum—and show how that one theorem specializes into König's and Menger's theorems and falls straight out of linear-programming duality.

Concept	Example	Description
Max-flow min-cut theorem	`\|f∗\| = min-cut capacity`	Maximum flow value equals minimum s-t cut capacity

The rest of this section is part of the full cheat sheet

Table 3: Ford-Fulkerson Method

The original max-flow recipe, and really a framework rather than a single algorithm: keep finding augmenting paths in the residual graph and saturating them until none remain. These rows cover the mechanics of augmentation and reverse edges, plus the two big caveats—it can fail to terminate on irrational capacities, and its O(EF) running time degrades badly when the flow value F is large.

Concept	Example	Description
Ford-Fulkerson method	`while ∃ augmenting path: augment`	Framework: repeatedly find and augment along s-t paths in residual graph

The rest of this section is part of the full cheat sheet

Table 4: Edmonds-Karp Algorithm

One small change to Ford-Fulkerson—always pick the shortest augmenting path via BFS instead of any path—buys a strongly polynomial O(VE²) bound that no longer depends on capacity values. The rows here explain the analysis behind that: shortest-path distances only ever grow, each edge can become critical at most O(V) times, and that caps the total number of augmentations.

Concept	Example	Description
Edmonds-Karp algorithm	Ford-Fulkerson + BFS shortest paths	• Uses BFS to find shortest (fewest edges) augmenting path • O(VE²)

The rest of this section is part of the full cheat sheet

Table 1: Flow Network Fundamentals

Concept	Example	Description
Flow network	`G=(V,E), s,t∈V, cap:E→ℝ≥0`	Directed graph with source s, sink t, non-negative edge capacities
Flow	`f(u,v) ∈ [0, cap(u,v)]`	Assignment satisfying capacity and conservation constraints
Capacity constraint	`0 ≤ f(u,v) ≤ cap(u,v)`	Flow on each edge cannot exceed its capacity
Flow conservation	`∑f(u,v) = ∑f(v,w) ∀v≠s,t`	Flow in equals flow out at every internal vertex
Value of flow	`\|f\| = ∑f(s,v)`	Total flow leaving source (or entering sink)
Residual graph	`Gf: cf(u,v)=cap(u,v)-f(u,v)`	• Graph of remaining capacities • adds backward edge with capacity f(u,v)
Residual capacity	`cf(u,v) = cap(u,v) - f(u,v)`	• Remaining capacity on forward edge • f(u,v) on backward edge
Augmenting path	`s→a→b→t` in `Gf`	Path from s to t in residual graph with all positive residual capacities
Bottleneck capacity	`Δ = min{cf(e) : e∈P}`	Minimum residual capacity along augmenting path P
s-t cut	`(S,T): s∈S, t∈T, S∪T=V`	• Partition of V • capacity = sum of caps of edges from S to T
Cut capacity	`cap(S,T) = ∑cap(u,v): u∈S,v∈T`	Sum of capacities of forward edges crossing the cut
Minimum cut	`min over all s-t cuts of cap(S,T)`	• Cut with smallest total capacity • equals max flow by theorem
Integral flow theorem	All `cap∈ℤ≥0 ⟹ ∃f∗∈ℤ≥0`	If all capacities are integers, there exists an integer-valued max flow
Skew symmetry	`f(u,v) = -f(v,u)`	Anti-symmetry property of flow on pairs of edges
Parallel edges	`cap[u][v] += c` per edge	• Multiple edges between same pair • handled by summing capacities in adjacency matrix

Table 2: Max-Flow Min-Cut Theorem

Concept	Example	Description
Max-flow min-cut theorem	`\|f∗\| = min-cut capacity`	Maximum flow value equals minimum s-t cut capacity

Table 3: Ford-Fulkerson Method

Concept	Example	Description
Ford-Fulkerson method	`while ∃ augmenting path: augment`	Framework: repeatedly find and augment along s-t paths in residual graph

Table 4: Edmonds-Karp Algorithm

Concept	Example	Description
Edmonds-Karp algorithm	Ford-Fulkerson + BFS shortest paths	• Uses BFS to find shortest (fewest edges) augmenting path • O(VE²)