Offensive Security Researcher & Quantum Cryptography Analyst

Maximum Flow Algorithm: Comprehensive Explanation and Implementation Guide

Abdul Wahab Junaid
Maximum Flow: Comprehensive Explanation and Implementation

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

How It Works

I describe the Ford-Fulkerson method (with Edmonds-Karp’s BFS refinement):

  1. I initialize the flow on every edge to 0.
  2. I build the residual graph, where each edge (u, v) with capacity c and current flow f has a residual capacity c - f in the forward direction, and a residual capacity f in the reverse direction (allowing me to “undo” flow).
  3. I search for an augmenting path from s to t in the residual graph — using breadth-first search (Edmonds-Karp) to guarantee polynomial time.
  4. If no augmenting path exists, I stop; the current flow is maximum.
  5. Otherwise, I find the minimum residual capacity along the found path, called the “bottleneck.”
  6. 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).
  7. 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:

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

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version