Data structures & algorithms4 min

Maximum Flow

Imagine a network of water pipes flowing from a water treatment plant (the Source) to a city (the Sink). Each pipe has a maximum capacity (e.g., it can only carry 10 gallons of water per minute). Some pipes merge together, and some pipes split apart.

The Maximum Flow problem asks: What is the absolute maximum amount of water we can push through this entire network from the Source to the Sink without exceeding the capacity of any single pipe?

The Flow Network

A Flow Network is a Directed Graph where:

  1. Each edge has a non-negative Capacity $c(u, v)$.
  2. Each edge carries a Flow $f(u, v)$ such that $0 \le f(u, v) \le c(u, v)$.
  3. Conservation of Flow: For every node (except Source and Sink), the total flow coming into the node must perfectly equal the total flow going out of the node. (Water cannot magically disappear or be created inside a random junction).

In this network, the max flow is 15. We push 10 from Source->A. From A, we push 10 to Sink. We push 5 from Source->B, and then 5 to Sink.

The Residual Graph

To solve the Max Flow problem, algorithms rely on a conceptual tool called the Residual Graph. When you push 5 units of flow through a pipe with capacity 10:

  • The remaining forward capacity is 5.
  • The algorithm creates a "ghost" reverse edge with capacity 5. This allows the algorithm to mathematically "undo" or redirect flow later if it realizes it made a suboptimal decision.

1. The Ford-Fulkerson Method

Ford-Fulkerson is technically a "method" rather than an algorithm because it does not specify exactly how to find a path.

The logic is beautifully simple:

  1. Find any path from Source to Sink in the Residual Graph where every edge has remaining capacity $> 0$. (This is called an Augmenting Path).
  2. Find the "Bottleneck" of this path (the edge with the smallest remaining capacity).
  3. Add the bottleneck value to the Total Flow.
  4. Update the residual capacities along the path (subtract from forward edges, add to reverse edges).
  5. Repeat until no more augmenting paths can be found!

2. Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method. It strictly uses Breadth-First Search (BFS) to find the augmenting path. By using BFS, it guarantees that it always picks the path with the fewest number of edges, avoiding pathological worst-case scenarios that can cause standard Ford-Fulkerson to loop almost infinitely.

Implementation (Edmonds-Karp in TypeScript)

typescript
function bfsFindPath(rGraph: number[][], s: number, t: number, parent: number[]): boolean {
  const V = rGraph.length;
  const visited = new Array(V).fill(false);
  const queue: number[] = [s];
  
  visited[s] = true;
  parent[s] = -1;

  while (queue.length > 0) {
    const u = queue.shift()!;
    
    for (let v = 0; v < V; v++) {
      // If not visited AND there is available capacity in the residual graph
      if (!visited[v] && rGraph[u][v] > 0) {
        // If we found the sink, path exists!
        if (v === t) {
          parent[v] = u;
          return true;
        }
        queue.push(v);
        parent[v] = u;
        visited[v] = true;
      }
    }
  }
  return false;
}

function edmondsKarp(graph: number[][], source: number, sink: number): number {
  const V = graph.length;
  // Create Residual Graph (Initially a clone of original capacities)
  const rGraph = graph.map(row => [...row]);
  const parent = new Array(V).fill(-1);
  let maxFlow = 0;

  // Augment the flow while there is a path from source to sink
  while (bfsFindPath(rGraph, source, sink, parent)) {
    // Find the bottleneck capacity of the path we just found
    let pathFlow = Infinity;
    for (let v = sink; v !== source; v = parent[v]) {
      const u = parent[v];
      pathFlow = Math.min(pathFlow, rGraph[u][v]);
    }

    // Update residual capacities of the edges and reverse edges
    for (let v = sink; v !== source; v = parent[v]) {
      const u = parent[v];
      rGraph[u][v] -= pathFlow; // Forward edge capacity drops
      rGraph[v][u] += pathFlow; // Reverse edge capacity grows! (Allows "undoing")
    }

    // Add path flow to overall flow
    maxFlow += pathFlow;
  }

  return maxFlow;
}
  • Time Complexity: $O(V \times E^2)$
  • Dinic's Algorithm (Alternative): A more complex variation that uses Level Graphs and Blocking Flows to achieve a blazing fast $O(V^2 \times E)$ time.