Problem 37.6 · Advanced Graph AlgorithmsHard

Maximum Flow

What it teaches: Edmonds-Karp: BFS augmenting paths in the residual graph.

In plain words

Water flows through pipes from a source to a sink, and each pipe can carry only so much. Find a path with room left (using BFS, the shortest one), push as much water as its tightest pipe allows, and repeat. Pushing water also creates "undo" room backwards, so later paths can reroute it.

Return the most water that can reach the sink. Example: n = 4, [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]], s = 0, t = 3 → 5.

The problem

Directed edges [u, v, capacity] connect n nodes. Return the maximum flow from s to t.

Example 1

Input: n = 4, edges = [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]], s = 0, t = 3
Output: 5

Constraints

2 ≤ n ≤ 100
Capacities ≤ 10⁶

Pattern clues in the wording

→ Capacities on edges, maximum throughput
→ Matching and cut problems in disguise

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public int maxFlow(int n, int[][] edges, int s, int t) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	n = 4 edges = [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]] s = 0 t = 3	5
2	n = 6 edges = [[0,1,16],[0,2,13],[1,2,10],[2,1,4],[1,3,12],[3,2,9],[2,4,14],[4,3,7],[3,5,20],[4,5,4]] s = 0 t = 5	23

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Edmonds-Karp · O(V × E²)

Edmonds-Karp

Time O(V × E²) Space O(V²)

Capacity matrix (parallel edges add up). BFS for a path with positive residual capacity, push its bottleneck, update both directions.

▶ Dry run: Edmonds-Karp: BFS augmenting pathsn = 4, edges = [[0,1,3],[0,2,2],[1,2,1],[1,3,2],[2,3,3]], s = 0, t = 3

flow(vars)

Step 1/5This example is already small (4 nodes), so we trace it in full. Edge labels show flow/capacity. Push water from 0 to 3.

Approach 1

import java.util.*;

class Solution {
    public int maxFlow(int n, int[][] edges, int s, int t) {
        int[][] cap = new int[n][n];
        for (int[] e : edges) cap[e[0]][e[1]] += e[2];
        int flow = 0;
        while (true) {
            int[] parent = new int[n];
            Arrays.fill(parent, -1);
            parent[s] = s;
            Deque<Integer> q = new ArrayDeque<>();
            q.offer(s);
            while (!q.isEmpty() && parent[t] == -1) {
                int u = q.poll();
                for (int v = 0; v < n; v++)
                    if (parent[v] == -1 && cap[u][v] > 0) { parent[v] = u; q.offer(v); }
            }
            if (parent[t] == -1) return flow;
            int push = Integer.MAX_VALUE;
            for (int v = t; v != s; v = parent[v]) push = Math.min(push, cap[parent[v]][v]);
            for (int v = t; v != s; v = parent[v]) { cap[parent[v]][v] -= push; cap[v][parent[v]] += push; }
            flow += push;
        }
    }
}

Verdict: Shortest augmenting paths guarantee termination.

Before you submit

Edge cases and common mistakes

Test these inputs

No path from s to t (0)
Parallel edges

Mistakes people make

Omitting reverse capacities (gets stuck below the maximum).

Interview

Follow-up questions

What does the minimum cut tell you?

Command Palette

The problem

Approaches

Edmonds-Karp

Edge cases and common mistakes

Follow-up questions