Network Flow from Scratch (2026)
Network flow algorithms compute the maximum amount of flow that can be sent from a source to a sink in a capacitated directed graph. The Ford-Fulkerson method and its practical variant Edmonds-Karp are foundational.
The max flow min cut theorem states that the maximum flow equals the capacity of the minimum cut, connecting flow optimization to graph partitioning.
Ford-Fulkerson Method
Ford-Fulkerson repeatedly finds an augmenting path from source to sink using any traversal (DFS/BFS) and pushes flow along it. The algorithm terminates when no augmenting path exists in the residual graph.
Its time complexity depends on the maximum flow value F, giving O(E * F) in the worst case, which can be exponential with poor path selection.
int fordFulkerson(vector>& capacity, int s, int t) {
int V = capacity.size(), flow = 0;
vector> residual = capacity;
while (true) {
vector parent(V, -1);
stack st; st.push(s); parent[s] = s;
while (!st.empty() && parent[t] == -1) {
int u = st.top(); st.pop();
for (int v = 0; v < V; v++)
if (parent[v] == -1 && residual[u][v] > 0)
parent[v] = u, st.push(v);
}
if (parent[t] == -1) break;
int bottleneck = INT_MAX;
for (int v = t; v != s; v = parent[v])
bottleneck = min(bottleneck, residual[parent[v]][v]);
for (int v = t; v != s; v = parent[v]) {
residual[parent[v]][v] -= bottleneck;
residual[v][parent[v]] += bottleneck;
}
flow += bottleneck;
}
return flow;
} Edmonds-Karp Algorithm
Edmonds-Karp is Ford-Fulkerson with BFS-based path selection, ensuring the shortest augmenting path (in terms of number of edges) is used. This guarantees O(V * E²) time complexity.
BFS path selection prevents the exponential worst-case of DFS-based Ford-Fulkerson, making Edmonds-Karp practical for moderate-sized graphs.
int edmondsKarp(vector>& capacity, int s, int t) {
int V = capacity.size(), flow = 0;
vector> residual = capacity;
while (true) {
vector parent(V, -1);
queue q; q.push(s); parent[s] = s;
while (!q.empty() && parent[t] == -1) {
int u = q.front(); q.pop();
for (int v = 0; v < V; v++)
if (parent[v] == -1 && residual[u][v] > 0)
parent[v] = u, q.push(v);
}
if (parent[t] == -1) break;
int bottleneck = INT_MAX;
for (int v = t; v != s; v = parent[v])
bottleneck = min(bottleneck, residual[parent[v]][v]);
for (int v = t; v != s; v = parent[v]) {
residual[parent[v]][v] -= bottleneck;
residual[v][parent[v]] += bottleneck;
}
flow += bottleneck;
}
return flow;
} Frequently Asked Questions
What is the max flow min cut theorem?
It states that the maximum flow value from source to sink equals the total capacity of the minimum cut separating source from sink. This bridges network flow and graph cut problems.
When should I use Edmonds-Karp over Ford-Fulkerson?
Use Edmonds-Karp (BFS-based) when the graph may cause DFS to take exponential time, as BFS guarantees O(V*E²) worst-case complexity regardless of capacities.
Originally published on Ayodhyyya. Last updated June 1, 2026.