Java Edmonds-Karp max flow: residual capacity and reverse edges

Last updated: 30 Sept 20264 min read

tutorial

Edmonds-Karp repeatedly finds a shortest augmenting path in the residual network, then updates forward and reverse capacities.

Reverse edges are part of the state

A path can later be rerouted. Decreasing only forward capacity would lose the ability to undo an earlier choice; adding the same amount to the reverse edge records that option. The fixture has total source capacity five and reaches flow five. It also checks a disconnected sink, which returns zero.

This matrix version treats vertices as a small fixed set and capacities as nonnegative longs. A production graph loader must validate vertex IDs, duplicate edges and sums before a flow run. Bipartite matching is a related unit-capacity case.

Do not confuse flow with a path

The result is total throughput under edge capacities, not the number of edges in one route or the cheapest path. Dijkstra answers a different optimization question.

Working program

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
public class ReceiptNetworkFlow {
    static long maximum(long[][] capacity, int source, int sink) {
        int size = capacity.length;
        if (size == 0 || source < 0 || sink < 0 || source >= size || sink >= size || source == sink)
            throw new IllegalArgumentException("endpoints");
        long[][] residual = new long[size][size];
        for (int from = 0; from < size; from++) {
            if (capacity[from].length != size) throw new IllegalArgumentException("square matrix");
            for (int to = 0; to < size; to++) {
                if (capacity[from][to] < 0) throw new IllegalArgumentException("capacity");
                residual[from][to] = capacity[from][to];
            }
        }
        long flow = 0;
        while (true) {
            int[] parent = new int[size];
            Arrays.fill(parent, -1);
            parent[source] = source;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(source);
            while (!queue.isEmpty() && parent[sink] == -1) {
                int from = queue.remove();
                for (int to = 0; to < size; to++)
                    if (parent[to] == -1 && residual[from][to] > 0) {
                        parent[to] = from;
                        queue.add(to);
                    }
            }
            if (parent[sink] == -1) return flow;
            long amount = Long.MAX_VALUE;
            for (int to = sink; to != source; to = parent[to])
                amount = Math.min(amount, residual[parent[to]][to]);
            for (int to = sink; to != source; to = parent[to]) {
                int from = parent[to];
                residual[from][to] -= amount;
                residual[to][from] = Math.addExact(residual[to][from], amount);
            }
            flow = Math.addExact(flow, amount);
        }
    }
    public static void main(String[] args) {
        long[][] network = {{0, 3, 2, 0}, {0, 0, 1, 2},
            {0, 0, 0, 3}, {0, 0, 0, 0}};
        System.out.println(maximum(network, 0, 3));
        if (maximum(new long[][]{{0, 0}, {0, 0}}, 0, 1) != 0)
            throw new AssertionError("disconnected sink");
    }
}

Output

Costs and boundaries

Edmonds-Karp has O(V E²) time for an adjacency-list graph. This matrix version scans V neighbors for each vertex: with O(V E) augmentations, its upper bound is O(V² + V³ E) time and O(V²) residual space. E counts positive-capacity arcs; sparse production graphs need a different representation.

Common Mistakes

Do not omit reverse residual capacity.
Do not treat negative or overflowing capacities as valid input.
Do not report a matrix scan as if it used an adjacency list.