I want to explain the maximum flow problem, where I am given a flow network — a directed graph with edge capacities, a source node, and a sink node — and I want to find the greatest possible amount of flow I can push from the source to the sink without violating any capacity constraint. I care about this problem because it models an enormous range of practical situations, from network bandwidth to transportation logistics, and because it connects deeply to the max-flow min-cut theorem, one of the most elegant results in combinatorial optimization.
History and Background
I credit the origin of the maximum flow problem to Tolstoi’s 1930s work on Soviet railway transportation planning, though the problem became formalized in the West through the work of T. E. Harris and F. S. Ross in the mid-1950s, motivated by analyzing the capacity of the Soviet railway network. Lester Ford Jr. and Delbert Fulkerson then developed the Ford-Fulkerson method in 1956, proving the max-flow min-cut theorem and giving the first general algorithm for the problem. Jack Edmonds and Richard Karp later refined the method in 1972 by specifying breadth-first search for augmenting paths, producing the Edmonds-Karp algorithm with a guaranteed polynomial running time.
Problem Statement
I define a flow network as a directed graph G = (V, E) where each edge (u, v) has a nonnegative capacity c(u, v), along with a designated source s and sink t. I want to find a flow function f(u, v) satisfying capacity constraints (0 ≤ f(u,v) ≤ c(u,v)) and flow conservation (inflow equals outflow at every vertex except s and t), such that the total flow leaving s (equivalently, arriving at t) is maximized.
Core Concepts
- Flow network: a directed graph with edge capacities, a source, and a sink.
- Flow: an assignment of values to edges representing the amount of “stuff” moving along each edge, respecting capacity and conservation constraints.
- Residual graph: a graph representing how much additional flow can still be pushed along each edge (and how much can be “undone” via reverse edges).
- Augmenting path: a path from
stotin the residual graph along which I can push additional flow. - Cut: a partition of the vertices into two sets, one containing
sand the other containingt; the cut’s capacity is the sum of capacities of edges crossing from the source side to the sink side. - Max-flow min-cut theorem: the maximum flow value in a network equals the minimum capacity of any
s–tcut.
How It Works
I describe the Ford-Fulkerson method (with Edmonds-Karp’s BFS refinement):
- I initialize the flow on every edge to 0.
- I build the residual graph, where each edge
(u, v)with capacitycand current flowfhas a residual capacityc - fin the forward direction, and a residual capacityfin the reverse direction (allowing me to “undo” flow). - I search for an augmenting path from
stotin the residual graph — using breadth-first search (Edmonds-Karp) to guarantee polynomial time. - If no augmenting path exists, I stop; the current flow is maximum.
- Otherwise, I find the minimum residual capacity along the found path, called the “bottleneck.”
- I increase the flow along each forward edge of the path by the bottleneck amount, and decrease the flow along each reverse edge by the bottleneck amount (equivalently, I update the residual capacities).
- I repeat steps 3–6 until no augmenting path remains.
Working Principle
I understand the core mechanism as repeatedly finding “room to grow” in the network. Each augmenting path represents a way to route additional flow from s to t, but I also need the ability to reroute — that’s what the reverse residual edges give me: if I later find that an earlier flow assignment was suboptimal, the algorithm can effectively cancel part of it by pushing flow backward along a reverse edge. This ability to “undo” earlier decisions through residual edges is what makes the greedy augmenting-path approach provably reach the true maximum flow, rather than getting stuck in a suboptimal local choice.
Mathematical Foundation
I define the value of a flow as the net flow out of the source:
$$ |f| = \sum_{v \in V} f(s, v) – \sum_{v \in V} f(v, s) $$
For any s–t cut $(S, T)$ (with $s \in S$, $t \in T$), the capacity of the cut is:
$$ c(S, T) = \sum_{u \in S, v \in T} c(u, v) $$
The max-flow min-cut theorem states:
$$ \max |f| = \min_{(S,T)} c(S, T) $$
The residual capacity of an edge is:
$$ c_f(u, v) = c(u, v) – f(u, v) $$
and for the reverse edge:
$$ c_f(v, u) = f(u, v) $$
Diagrams
flowchart TD
A["Initialize flow f = 0 on all edges"] --> B["Build residual graph"]
B --> C["BFS: find augmenting path s to t"]
C --> D{"Path found?"}
D -- No --> E["Stop: current flow is maximum"]
D -- Yes --> F["Find bottleneck capacity along path"]
F --> G["Update flow and residual capacities along path"]
G --> B
Pseudocode
EDMONDS-KARP(G, s, t)
for each edge (u, v) in G
f[u][v] = 0
while there exists a path p from s to t in residual graph G_f, found via BFS
c_f(p) = min residual capacity of edges along p
for each edge (u, v) in p
f[u][v] = f[u][v] + c_f(p)
f[v][u] = f[v][u] - c_f(p)
return f
Step-by-Step Example
I use a small network with source S, sink T, and intermediate nodes A, B:
S → Acapacity 3S → Bcapacity 2A → Bcapacity 1A → Tcapacity 2B → Tcapacity 3
Iteration 1: BFS finds path S → A → T with bottleneck min(3, 2) = 2. I push 2 units of flow along this path. Residual capacities update: S→A becomes 1, A→T becomes 0 (and reverse edges A→S becomes 2, T→A becomes 2).
Iteration 2: BFS finds path S → B → T with bottleneck min(2, 3) = 2. I push 2 units. Residual capacities update: S→B becomes 0, B→T becomes 1.
Iteration 3: BFS finds path S → A → B → T with bottleneck min(1, 1, 1) = 1. I push 1 unit. Residual capacities update accordingly.
Iteration 4: BFS finds no more augmenting paths from S to T (all outgoing capacity from S is exhausted: S→A and S→B are both 0).
Total flow: 2 + 2 + 1 = 5. I can verify this matches the min cut: the cut separating {S} from everything else has capacity 3 + 2 = 5, confirming by the max-flow min-cut theorem that 5 is indeed the maximum flow.
Time Complexity
- Ford-Fulkerson (generic, using DFS for augmenting paths): $O(E \cdot f^*)$, where
f*is the value of the maximum flow — this can be very slow if capacities are large integers, since each augmenting path might only increase the flow by 1 unit in the worst case. - Edmonds-Karp (BFS for augmenting paths): $O(V E^2)$, a polynomial bound independent of the capacity values, since I can prove that the number of augmentations is bounded by $O(VE)$ when I always choose shortest augmenting paths.
- Dinic’s algorithm (a further refinement not detailed here): $O(V^2 E)$, faster still for many graph classes.
- These bounds represent worst-case behavior; in practice, especially on sparse or well-structured graphs, both algorithms often perform significantly better than their worst-case bounds suggest.
Space Complexity
I need $O(V + E)$ space to store the graph and its residual capacities (typically as an adjacency matrix, $O(V^2)$, or adjacency list, $O(V + E)$, depending on implementation choice), plus $O(V)$ additional space for BFS bookkeeping (visited array, parent pointers, and the queue).
Correctness Analysis
I justify correctness through the max-flow min-cut theorem: the algorithm terminates precisely when no augmenting path exists in the residual graph, which happens exactly when the set of vertices reachable from s in the residual graph (call it S) and its complement (call it T) form an s–t cut whose capacity equals the current flow value. Since I already know (by the weak duality-style argument that any flow value is at most any cut’s capacity) that flow value ≤ cut capacity always holds, finding a flow whose value equals some cut’s capacity proves that flow is maximum — I have simultaneously found the optimal flow and a matching minimum cut, which certifies optimality.
Advantages
- I get a provably correct algorithm with a clean theoretical foundation (max-flow min-cut duality).
- Edmonds-Karp guarantees polynomial time, independent of the specific capacity values.
- The residual graph technique generalizes naturally to many related problems (bipartite matching, edge-disjoint paths, project selection, and more).
- Implementation is relatively straightforward once I understand the residual graph concept.
Disadvantages
- Basic Ford-Fulkerson (without BFS) can be extremely slow — even non-terminating in adversarial cases with irrational capacities — if I choose augmenting paths poorly.
- Edmonds-Karp’s $O(VE^2)$ bound, while polynomial, is not the fastest known algorithm; more advanced algorithms (Dinic’s, push-relabel) scale better on large or dense graphs.
- The algorithm only computes the flow value and one valid flow assignment; extracting all minimum cuts or all maximum flows requires additional work.
Applications
- Network bandwidth allocation: modeling the maximum data throughput achievable across a network.
- Bipartite matching: maximum matching problems can be reduced to a maximum flow computation.
- Airline scheduling: modeling crew and aircraft assignment problems as flow networks.
- Image segmentation: min-cut/max-flow methods are widely used in computer vision for foreground/background separation.
- Project selection problems: maximizing profit subject to prerequisite constraints, modeled as a flow network (the “project selection problem”).
- Circulation problems in supply chains: modeling the movement of goods subject to capacity constraints.
Implementation in C
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define V 6 /* number of vertices */
/* I use an adjacency matrix to store residual capacities */
int graph[V][V];
/* I run BFS to find an augmenting path, filling parent[] to reconstruct it.
Returns 1 if a path from s to t exists in the residual graph. */
int bfs(int residual[V][V], int s, int t, int parent[V]) {
int visited[V];
memset(visited, 0, sizeof(visited));
int queue[V], front = 0, back = 0;
queue[back++] = s;
visited[s] = 1;
parent[s] = -1;
while (front < back) {
int u = queue[front++];
for (int v = 0; v < V; v++) {
if (!visited[v] && residual[u][v] > 0) {
queue[back++] = v;
visited[v] = 1;
parent[v] = u;
if (v == t) {
return 1;
}
}
}
}
return 0;
}
/* I implement Edmonds-Karp: Ford-Fulkerson using BFS for augmenting paths */
int edmondsKarp(int graph[V][V], int s, int t) {
int residual[V][V];
memcpy(residual, graph, sizeof(residual));
int parent[V];
int maxFlow = 0;
while (bfs(residual, s, t, parent)) {
/* I find the bottleneck capacity along the found path */
int pathFlow = INT_MAX;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
if (residual[u][v] < pathFlow) {
pathFlow = residual[u][v];
}
}
/* I update residual capacities along the path (forward and reverse) */
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
residual[u][v] -= pathFlow;
residual[v][u] += pathFlow;
}
maxFlow += pathFlow;
}
return maxFlow;
}
int main(void) {
/* Vertices: 0=S, 1=A, 2=B, 3=T (I use indices 0-3 within a 6x6 array for generality) */
memset(graph, 0, sizeof(graph));
graph[0][1] = 3; /* S -> A */
graph[0][2] = 2; /* S -> B */
graph[1][2] = 1; /* A -> B */
graph[1][3] = 2; /* A -> T */
graph[2][3] = 3; /* B -> T */
int source = 0, sink = 3;
int maxFlow = edmondsKarp(graph, source, sink);
printf("The maximum possible flow from S to T is: %d\n", maxFlow);
return 0;
}
I represented the graph as an adjacency matrix for simplicity, which is fine for small, dense graphs but would be better replaced with an adjacency list for large sparse networks. The bfs function both finds an augmenting path and records how to reconstruct it through the parent array, and edmondsKarp repeatedly calls it, updating residual capacities until no augmenting path remains.
Sample Input and Output
Input: network with S→A(3), S→B(2), A→B(1), A→T(2), B→T(3).
Output:
The maximum possible flow from S to T is: 5
which matches my hand-traced example above.
Optimization Techniques
- Dinic’s algorithm: I build level graphs via BFS and find blocking flows via DFS, achieving $O(V^2 E)$ time, faster than plain Edmonds-Karp on most graphs.
- Push-relabel algorithms: I maintain a “preflow” and push excess flow locally, achieving $O(V^2 E)$ or better with the right heuristics (e.g., highest-label push-relabel).
- Scaling algorithms: I process augmenting paths in decreasing order of capacity “scale,” improving practical performance on graphs with a wide range of capacities.
- Adjacency list representation: for sparse graphs, I switch from an adjacency matrix ($O(V^2)$ space) to an adjacency list ($O(V+E)$ space) to reduce memory usage and speed up iteration.
- Unit-capacity graphs: for special cases like bipartite matching, I exploit unit capacities to get faster specialized bounds, such as $O(E\sqrt{V})$ with the Hopcroft-Karp-style approach.
Common Mistakes
- Forgetting to add reverse edges (with initial capacity 0) when building the residual graph, which prevents the algorithm from “undoing” earlier flow decisions and can lead to a suboptimal result.
- Using DFS instead of BFS for augmenting paths and assuming polynomial-time behavior — that guarantee specifically requires BFS (shortest augmenting paths), which is the “Edmonds-Karp” refinement.
- Miscomputing the bottleneck capacity by not checking every edge along the path.
- Forgetting to update both the forward and reverse residual capacities when pushing flow along a path.
- Confusing flow value with total capacity — the source’s outgoing capacity is an upper bound, not necessarily the achievable maximum flow.
Further Reading
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, Chapter 26 (Maximum Flow): https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Ford, Fulkerson — Flows in Networks: https://press.princeton.edu/books/paperback/9780691146676/flows-in-networks
- Edmonds, Karp — “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems,” Journal of the ACM, 1972: https://dl.acm.org/doi/10.1145/321694.321699
- Dinic — “Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation,” Soviet Mathematics Doklady, 1970: https://www.cs.bgu.ac.il/~dinitz/D70.pdf
- Stanford CS161 lecture notes on network flow: https://web.stanford.edu/class/cs161/
