Implement Maximum Flow: Edmonds–Karp in Six Languages

A directed network has n nodes numbered 0 to n − 1. Each triple [u, v, c] in edges is an edge from u to v with capacity c; the same pair may appear more than once, and both [u, v, …] and [v, u, …] may be present. Return the maximum flow from source to sink: the largest total that can leave the source when no edge carries more than its capacity and every other node passes on exactly what it receives.

Examples

Input	Output	Why
`n = 4, edges = [[0,1,1],[0,2,1],[1,2,1],[1,3,1],[2,3,1]], source = 0, sink = 3`	`2`	0 → 1 → 3 and 0 → 2 → 3.
`n = 3, edges = [[0,1,5]], source = 0, sink = 2`	`0`	Nothing reaches the sink.
`n = 4, edges = [[0,1,3],[0,1,4],[1,3,5],[0,2,2],[2,3,9]], source = 0, sink = 3`	`7`	Parallel edges add up to 7 into node 1, but 1 → 3 carries only 5; 2 more go through node 2.

Constraints

2 ≤ n ≤ 100
0 ≤ edges.length ≤ 1000
1 ≤ c ≤ 10⁶
source ≠ sink

Hints

Hint 1

Keep a matrix of residual capacities: res[u][v] starts as the total capacity from u to v (summing parallel edges).

Hint 2

Repeatedly find a path from source to sink with res > 0 on every step, using breadth-first search, and push its bottleneck.

Hint 3

Pushing b along u → v means res[u][v] -= b and res[v][u] += b. The second update is the reverse edge that lets a later path undo this one.

Where people lose marks

Forgetting the reverse update res[v][u] += b, which makes the algorithm greedy and wrong.
Overwriting rather than adding parallel edges: two edges 0 → 1 of capacity 3 and 4 give 7.
Searching depth-first with large capacities: the number of rounds can grow with the size of the flow.

Dry run on `6,[[0,1,10],[0,2,10],[1,3,4],[1,2,2],[1,4,8],[2,4,9],[4,3,6],[3,5,10],[4,5,10]],0,5`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

total0
Every edge is labelled flow/capacity, all flows 0. Look for a path from 0 to 5 with spare capacity on every step.
Step 2 / 6

total4
Augmenting path 0 → 1 → 3 → 5, bottleneck 4: push 4 more units. Total flow 4.
Step 3 / 6

total10
Augmenting path 0 → 1 → 4 → 5, bottleneck 6: push 6 more units. Total flow 10.
Step 4 / 6

total14
Augmenting path 0 → 2 → 4 → 5, bottleneck 4: push 4 more units. Total flow 14.
Step 5 / 6

total19
Augmenting path 0 → 2 → 4 → 3 → 5, bottleneck 5: push 5 more units. Total flow 19.
Step 6 / 6

total19
No augmenting path is left: the maximum flow is 19. The nodes still reachable from 0 through spare capacity (shaded) form one side of a minimum cut; the cut edges (red) are full and their capacities add to 19.

How to think about it

Ford–Fulkerson with breadth-first search (Edmonds–Karp). A residual capacity matrix holds, for every ordered pair, how much more can be sent from u to v. It starts as the sum of the capacities of the edges from u to v.

Search from the source, following only pairs with positive residual capacity, recording each node's predecessor. If the sink is not reached, stop.
Walk back from the sink to find the bottleneck, the smallest residual capacity on the path.
Walk back again, subtracting the bottleneck forward and adding it backward. Add it to the answer.

The backward addition is the reverse edge: it records that this flow can later be cancelled and rerouted. Using shortest augmenting paths bounds the number of rounds at O(n · m), independent of the capacities.

Complexity. Time O(n³ · m) with a matrix · Space O(n²)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

from collections import deque

def max_flow(n, edges, source, sink):
    res = [[0] * n for _ in range(n)]       # residual capacities
    for u, v, c in edges:
        res[u][v] += c                       # parallel edges add up
    total = 0
    while True:
        prev = [-1] * n
        prev[source] = source
        q = deque([source])
        while q and prev[sink] == -1:        # shortest augmenting path
            u = q.popleft()
            for v in range(n):
                if prev[v] == -1 and res[u][v] > 0:
                    prev[v] = u
                    q.append(v)
        if prev[sink] == -1:
            return total                     # no augmenting path left
        b, v = float('inf'), sink
        while v != source:                   # bottleneck
            b = min(b, res[prev[v]][v])
            v = prev[v]
        v = sink
        while v != source:                   # push, and open the reverse edge
            res[prev[v]][v] -= b
            res[v][prev[v]] += b
            v = prev[v]
        total += b

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>

long long solve(int n, const std::vector<std::vector<int>>& edges, int source, int sink) {
    std::vector<std::vector<long long>> res(n, std::vector<long long>(n, 0));   // residual capacities
    for (const auto& e : edges) res[e[0]][e[1]] += e[2];                         // parallel edges add up
    long long total = 0;
    for (;;) {
        std::vector<int> prev(n, -1);
        prev[source] = source;
        std::queue<int> q;
        q.push(source);
        while (!q.empty() && prev[sink] == -1) {                                 // shortest augmenting path
            int u = q.front();
            q.pop();
            for (int v = 0; v < n; ++v)
                if (prev[v] == -1 && res[u][v] > 0) { prev[v] = u; q.push(v); }
        }
        if (prev[sink] == -1) return total;
        long long b = LLONG_MAX;
        for (int v = sink; v != source; v = prev[v]) b = std::min(b, res[prev[v]][v]);
        for (int v = sink; v != source; v = prev[v]) { res[prev[v]][v] -= b; res[v][prev[v]] += b; }
        total += b;
    }
}

import java.util.*;

class Solution {
    public long maxFlow(int n, int[][] edges, int source, int sink) {
        long[][] res = new long[n][n];                     // residual capacities
        for (int[] e : edges) res[e[0]][e[1]] += e[2];     // parallel edges add up
        long total = 0;
        while (true) {
            int[] prev = new int[n];
            Arrays.fill(prev, -1);
            prev[source] = source;
            ArrayDeque<Integer> q = new ArrayDeque<>();
            q.add(source);
            while (!q.isEmpty() && prev[sink] == -1) {     // shortest augmenting path
                int u = q.poll();
                for (int v = 0; v < n; v++)
                    if (prev[v] == -1 && res[u][v] > 0) { prev[v] = u; q.add(v); }
            }
            if (prev[sink] == -1) return total;
            long b = Long.MAX_VALUE;
            for (int v = sink; v != source; v = prev[v]) b = Math.min(b, res[prev[v]][v]);
            for (int v = sink; v != source; v = prev[v]) { res[prev[v]][v] -= b; res[v][prev[v]] += b; }
            total += b;
        }
    }
}

function maxFlow(n, edges, source, sink) {
  const res = Array.from({ length: n }, () => new Array(n).fill(0));   // residual capacities
  for (const [u, v, c] of edges) res[u][v] += c;                       // parallel edges add up
  let total = 0;
  for (;;) {
    const prev = new Array(n).fill(-1);
    prev[source] = source;
    const q = [source];
    for (let head = 0; head < q.length && prev[sink] === -1; head++) {   // shortest augmenting path
      const u = q[head];
      for (let v = 0; v < n; v++) if (prev[v] === -1 && res[u][v] > 0) { prev[v] = u; q.push(v); }
    }
    if (prev[sink] === -1) return total;
    let b = Infinity;
    for (let v = sink; v !== source; v = prev[v]) b = Math.min(b, res[prev[v]][v]);
    for (let v = sink; v !== source; v = prev[v]) { res[prev[v]][v] -= b; res[v][prev[v]] += b; }   // reverse edge
    total += b;
  }
}

use std::collections::VecDeque;

fn solve(n: i64, edges: &[[i64; 3]], source: i64, sink: i64) -> i64 {
    let (n, s, t) = (n as usize, source as usize, sink as usize);
    let mut res = vec![vec![0i64; n]; n];                 // residual capacities
    for e in edges {
        res[e[0] as usize][e[1] as usize] += e[2];        // parallel edges add up
    }
    let mut total = 0;
    loop {
        let mut prev = vec![usize::MAX; n];
        prev[s] = s;
        let mut q = VecDeque::from([s]);
        while let Some(u) = q.pop_front() {               // shortest augmenting path
            if prev[t] != usize::MAX {
                break;
            }
            for v in 0..n {
                if prev[v] == usize::MAX && res[u][v] > 0 {
                    prev[v] = u;
                    q.push_back(v);
                }
            }
        }
        if prev[t] == usize::MAX {
            return total;
        }
        let mut b = i64::MAX;
        let mut v = t;
        while v != s {
            b = b.min(res[prev[v]][v]);
            v = prev[v];
        }
        v = t;
        while v != s {
            res[prev[v]][v] -= b;
            res[v][prev[v]] += b;                         // reverse edge
            v = prev[v];
        }
        total += b;
    }
}

import qualified Data.Map.Strict as M
import Data.Sequence (Seq (..), (|>))
import qualified Data.Sequence as Q

solve :: Int -> [[Int]] -> Int -> Int -> Int
solve n edges s t = go (M.fromListWith (+) [((u, v), c) | [u, v, c] <- edges]) 0
  where
    cap res u v = M.findWithDefault 0 (u, v) res
    -- breadth-first search for a shortest augmenting path; returns predecessors
    bfs res = loop (Q.singleton s) (M.singleton s s)
      where
        loop Empty prev = prev
        loop (u :<| q) prev
          | M.member t prev = prev
          | otherwise =
              let next = [v | v <- [0 .. n - 1], not (M.member v prev), cap res u v > 0]
              in loop (foldl (|>) q next) (foldr (\v -> M.insert v u) prev next)
    go res total = case M.lookup t prev of
        Nothing -> total
        Just _ -> go res' (total + b)
      where
        prev = bfs res
        path = takeWhile (\(u, v) -> u /= v) [(prev M.! v, v) | v <- iterate (prev M.!) t]
        b = minimum [cap res u v | (u, v) <- path]
        res' = foldr (\(u, v) r -> M.insertWith (+) (v, u) b (M.insert (u, v) (cap r u v - b) r)) res path

Variants to try

Return the edges of a minimum cut: after the last search, edges from reached to unreached nodes.
Count the edge-disjoint paths from source to sink (every capacity 1).
Nodes have capacities too: split each node into an in-node and an out-node joined by an edge of that capacity.

Next problems

Easy12 min

Maximum flow through a network

Examples

Constraints

Hints

Where people lose marks

Dry run on `6,[[0,1,10],[0,2,10],[1,3,4],[1,2,2],[1,4,8],[2,4,9],[4,3,6],[3,5,10],[4,5,10]],0,5`

How to think about it

The solution, in six languages

Variants to try

Next problems

Count the islands in a grid

Does an undirected graph contain a cycle?

Can the graph be split in two?

Keep going

Count the islands in a grid

Does an undirected graph contain a cycle?

Can the graph be split in two?

The pattern behind it

Maximum flow through a network

Examples

Constraints

Hints

Where people lose marks

Dry run on 6,[[0,1,10],[0,2,10],[1,3,4],[1,2,2],[1,4,8],[2,4,9],[4,3,6],[3,5,10],[4,5,10]],0,5

How to think about it

The solution, in six languages

Variants to try

Next problems

Count the islands in a grid

Does an undirected graph contain a cycle?

Can the graph be split in two?

Keep going

Count the islands in a grid

Does an undirected graph contain a cycle?

Can the graph be split in two?

The pattern behind it

Dry run on `6,[[0,1,10],[0,2,10],[1,3,4],[1,2,2],[1,4,8],[2,4,9],[4,3,6],[3,5,10],[4,5,10]],0,5`