Chapter 112

Home

Refactoring: Edmonds-Karp

Ford-Fulkerson uses DFS — can be slow (O(F×E)). Edmonds-Karp uses BFS to find the shortest augmenting path in terms of edges, guaranteeing O(V×E²) time regardless of flow value.

Before: DFS (Ford-Fulkerson) — O(F×E)

C++ — DFS-based

long long dfs(int u, int t, long long f) { ... }  // may take long paths

After: BFS (Edmonds-Karp) — O(V×E²)

C++ — Edmonds-Karp (BFS)

long long edmonds_karp(int s, int t) {
    int n = adj.size();
    long long flow = 0;

    while (true) {
        vector parent(n, -1), edge_idx(n, -1);
        queue q; q.push(s);

        // BFS to find shortest augmenting path
        while (!q.empty() && parent[t] == -1) {
            int u = q.front(); q.pop();
            for (int i = 0; i < adj[u].size(); i++) {
                auto& e = adj[u][i];
                if (parent[e.v] == -1 && e.v != s && e.cap > 0) {
                    parent[e.v] = u;
                    edge_idx[e.v] = i;
                    q.push(e.v);
                }
            }
        }
        if (parent[t] == -1) break;

        long long pushed = LLONG_MAX;
        for (int v = t; v != s; v = parent[v])
            pushed = min(pushed, adj[parent[v]][edge_idx[v]].cap);

        for (int v = t; v != s; v = parent[v]) {
            auto& e = adj[parent[v]][edge_idx[v]];
            e.cap -= pushed;
            adj[v][e.rev].cap += pushed;
        }
        flow += pushed;
    }
    return flow;
}

// O(V × E²) — works for V ≤ 1000, E ≤ 10000.

Key Takeaways