Ford-Fulkerson Max Flow

How Ford-Fulkerson works

You have a directed graph where every edge has a capacity — say, the maximum number of cars per minute it can carry, or the bandwidth in Mb/s. You're given a source s and a sink t. The question is: what's the maximum total flow from s to t such that no edge carries more than its capacity, and at every interior vertex the inflow equals the outflow?

Ford and Fulkerson's 1956 idea was startlingly simple. Find any path from s to t where every edge still has spare capacity (an "augmenting path"). Push flow equal to the bottleneck — the minimum spare capacity on that path. Repeat. When no augmenting path exists, the current flow is provably maximum.

The clever piece is the residual graph. After pushing 5 units along edge u → v with capacity 10, the residual graph still has u → v with remaining capacity 5 (forward residual), and also a new backward edge v → u with capacity 5 (representing the option to "cancel" some of the pushed flow). Future augmenting paths can use either direction. Without backward edges the algorithm would be a greedy first-come-first-served scheme that gets stuck in local optima. With them, it's globally optimal.

Why it's optimal — the min-cut connection

An s-t cut is a partition of the vertices into two sets S and T with s ∈ S and t ∈ T. The capacity of the cut is the sum of capacities of edges going from S to T. Every flow from s to t is bounded above by every cut's capacity.

The max-flow min-cut theorem says the bound is tight: max flow = min cut. When Ford-Fulkerson terminates, look at the vertices still reachable from s in the residual graph. Call that set S. Every edge from S to V \ S in the original graph must be saturated (otherwise it'd be in the residual graph), and every edge from V \ S to S must carry zero flow. The total flow equals the capacity of this cut. So the cut is minimum and the flow is maximum, simultaneously.

When to use Ford-Fulkerson (or its descendants)

• Bipartite matching: assign workers to jobs, students to schools, ads to slots.
• Edge- or vertex-disjoint path counting (Menger's theorem).
• Project-selection / minimum-cut classification: which subset of binary decisions maximises profit subject to dependencies.
• Image segmentation as min-cut on a pixel grid (Boykov-Kolmogorov).
• Sports elimination problems, baseball scheduling, course-allocation.

For real production systems with millions of edges, use Dinic's or push-relabel — Edmonds-Karp's O(VE²) is unfair on dense graphs. For sparse graphs and small E, modern Dinic's beats commercial LP solvers on max-flow LPs by 10-100×.

Ford-Fulkerson vs Edmonds-Karp vs Dinic's vs Push-Relabel

	Ford-Fulkerson	Edmonds-Karp	Dinic's	Push-Relabel (HL)
Worst-case time	O(E · max-flow)	O(V · E²)	O(V² · E)	O(V² · √E)
Unit-cap bipartite	O(VE) (essentially Hopcroft-Karp lower bound)	Same as bipartite-matching baseline	O(E · √V) — Hopcroft-Karp	Same as Dinic's order
Augmenting path strategy	Any (DFS by default)	Shortest by edge count (BFS)	Layered BFS + blocking flow	Local re-labeling, no paths
Terminates on irrationals?	No (Zwick counterexample)	Yes	Yes	Yes
Practical on 10^5 edges	Slow if max-flow large	Acceptable	Fast	Fastest in practice
Ease of implementation	Easiest (DFS + residual)	Easy (replace DFS with BFS)	Medium (layered graph + DFS)	Hard (excess + heights + gap relabel)
Used by	Textbook proofs, didactics	Most contest templates	BWA, Boost Graph, OR tools	Goldberg's HIPR, image-seg libs

If you only memorise one: Dinic's. It's the algorithm of choice for competitive programming, runs faster in practice than its O(V²E) worst case suggests, and reduces to Hopcroft-Karp's O(E √V) on unit-capacity graphs — fast enough for 10^5-vertex bipartite matching in a 1-second time limit.

Pseudo-code (Ford-Fulkerson with DFS)

function fordFulkerson(graph, s, t):
    flow = 0
    residual = copy(graph.capacities)         # residual[u][v] = remaining capacity

    while true:
        path, bottleneck = findAugmentingPath(residual, s, t)
        if path is None: break

        flow += bottleneck
        for (u, v) in path:
            residual[u][v] -= bottleneck      # forward edge: less capacity
            residual[v][u] += bottleneck      # backward edge: more capacity

    return flow

function findAugmentingPath(residual, s, t):
    # DFS or BFS from s, only following edges with residual capacity > 0
    parent = dfs(residual, s, t)
    if t not in parent: return None, 0
    bottleneck = min residual[u][v] over the s->t path
    return reconstructPath(parent, s, t), bottleneck

JavaScript implementation — bipartite matching via max flow

The textbook reduction: model the bipartite graph as a flow network with super-source and super-sink, run max flow, and read off the matching.

// Ford-Fulkerson with BFS (Edmonds-Karp) on adjacency matrix
function maxFlow(cap, s, t) {
  const n = cap.length;
  const res = cap.map(row => row.slice());   // residual
  let flow = 0;

  while (true) {
    const parent = new Int32Array(n).fill(-1);
    parent[s] = s;
    const queue = [s];
    while (queue.length && parent[t] === -1) {
      const u = queue.shift();
      for (let v = 0; v < n; v++) {
        if (parent[v] === -1 && res[u][v] > 0) {
          parent[v] = u;
          queue.push(v);
        }
      }
    }
    if (parent[t] === -1) break;

    // Bottleneck along the BFS path
    let bn = Infinity;
    for (let v = t; v !== s; v = parent[v]) bn = Math.min(bn, res[parent[v]][v]);
    for (let v = t; v !== s; v = parent[v]) {
      res[parent[v]][v] -= bn;
      res[v][parent[v]] += bn;
    }
    flow += bn;
  }
  return { flow, residual: res };
}

// Bipartite matching: leftSize × rightSize compatibility matrix
function bipartiteMatching(left, right, edges) {
  const S = 0, T = 1 + left + right;             // super-source, super-sink
  const N = T + 1;
  const cap = Array.from({ length: N }, () => new Int32Array(N));
  for (let i = 1; i <= left; i++)  cap[S][i] = 1;
  for (let j = 1; j <= right; j++) cap[left + j][T] = 1;
  for (const [u, v] of edges)      cap[u][left + v] = 1;
  return maxFlow(cap, S, T).flow;                // matching size
}

Adjacency matrices are clean for tiny graphs but cost O(V²) memory. For thousands of vertices, switch to an adjacency-list residual structure where each edge stores a reference to its reverse — Dinic's implementations do this routinely.

Python implementation — Edmonds-Karp on an adjacency list

from collections import defaultdict, deque

class FlowNetwork:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(dict)   # graph[u][v] = capacity

    def add_edge(self, u, v, cap):
        self.graph[u][v] = self.graph[u].get(v, 0) + cap
        self.graph[v].setdefault(u, 0)   # reverse edge starts at 0 capacity

    def bfs(self, s, t, parent):
        visited = {s}
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v, cap in self.graph[u].items():
                if v not in visited and cap > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == t:
                        return True
                    queue.append(v)
        return False

    def edmonds_karp(self, s, t):
        flow = 0
        parent = {}
        while self.bfs(s, t, parent):
            # bottleneck along the path
            v, bn = t, float("inf")
            while v != s:
                u = parent[v]
                bn = min(bn, self.graph[u][v])
                v = u
            # update residuals
            v = t
            while v != s:
                u = parent[v]
                self.graph[u][v] -= bn
                self.graph[v][u] += bn
                v = u
            flow += bn
            parent.clear()
        return flow

# Bipartite matching: 4 students, 4 schools, edges = preferences
g = FlowNetwork(10)
S, T = 0, 9
for student in range(1, 5):
    g.add_edge(S, student, 1)
for school in range(5, 9):
    g.add_edge(school, T, 1)
for u, v in [(1, 5), (1, 6), (2, 6), (3, 7), (4, 7), (4, 8)]:
    g.add_edge(u, v, 1)

print(g.edmonds_karp(S, T))   # max matching size

For the matching reduction the graph has O(V) edges with capacity 1, so Edmonds-Karp runs in O(V·E²) but with the |max-flow| factor capped by min(|left|, |right|). Practical runtime on 10^4 students × 10^4 schools with sparse preferences: under one second.

Variants and design choices

The pathological irrational case

If capacities are irrational, naive Ford-Fulkerson can pick augmenting paths whose total flow is a divergent geometric series — pushing 1, then 1/φ, then 1/φ², ... and never reaching the true maximum. The 1968 Ford-Fulkerson book gives such an example with capacity √5/2; the algorithm runs forever and converges to a flow strictly less than the maximum. Edmonds-Karp's BFS rule eliminates this: shortest-path augmentation guarantees termination regardless of capacities.

Capacity scaling

Process augmenting paths in decreasing scaling rounds: only augment along paths where the bottleneck is at least 2^k for the current k, then halve k. This is O(E² log U) where U is the maximum capacity — a strict improvement over basic Ford-Fulkerson on graphs with very large but balanced capacities.

Dinic's blocking flow

Dinic's algorithm builds a layered BFS graph from s and finds a "blocking flow" (a set of paths that saturate at least one edge each per s-t path) in one pass. Then re-BFSes and repeats. Worst case O(V²E), but on unit-capacity graphs it collapses to O(E √V) — the same bound as Hopcroft-Karp and the dominant choice for bipartite matching with up to ~10^5 vertices.

Push-relabel

Drops the global path-finding entirely. Maintain a "preflow" (where vertices can have excess) and a height function. Push excess flow downhill; if you can't push, raise the height. Goldberg-Tarjan's highest-label variant runs in O(V²√E) and dominates Dinic's on dense graphs in practice. Used in image segmentation, where graphs have 10^6+ vertices.

Min-cost max flow

If edges have both capacity and cost, you can run successive-shortest-path (replace BFS with Bellman-Ford or Dijkstra with potentials) to find a minimum-cost maximum flow. Used in transportation problems and assignment with preferences. Roughly O(F · (V + E) log V) per unit of flow with Dijkstra and Johnson's potentials.

Boykov-Kolmogorov for vision

A specialised augmenting-path algorithm tuned for grid-like graphs in computer vision. Maintains two search trees (from source and sink) that grow towards each other and merge. Empirically faster than push-relabel on the kinds of regular grids that arise in pixel labeling, even though its worst case is no better than O(VE²).

Common bugs and edge cases

• Forgetting backward edges. Without v → u with capacity equal to flow pushed, the algorithm becomes a greedy heuristic and gives wrong answers on graphs where re-routing helps.
• Multiple parallel edges between the same pair. Adjacency-matrix code collapses them into a single edge by overwriting; use additive capacity (cap[u][v] += new_cap) or switch to an adjacency-list edge structure.
• Negative residual values. Floating-point capacities accumulate rounding error; the residual can drift to −1e-12 and cause infinite loops. Use rational arithmetic, or epsilon-threshold the augmenting-path admissibility check.
• Source equals sink. Edge case: max flow is +∞ (or undefined). Validate inputs.
• Self-loops. u → u with positive capacity is unusual but legal. They never affect max flow but break some implementations that assume u != v in the augmenting-path inner loop.
• Bipartite matching with O(V) augmenting passes in Python. A naive BFS-per-edge implementation hits Python's interpreter overhead at n = 10^4. Use an adjacency-list with arrays of integers (not dicts) and cache the residual array — easy 10× speedup.
• Augmenting along zero-capacity edges. Always check residual[u][v] > 0 before relaxing v in BFS. Skipping the check causes the bottleneck to come out as 0 and the loop to spin without progress.