← all categories

Edmonds Karp 69f9586e

Edmonds-Karp max flow (BFS augmenting paths), same edge-list interface as dinic.h. Simpler to type but strictly worse complexity — prefer dinic.h unless V and E are both small.

Time: O(VE^2). tested

content/flows/edmonds-karp.h

template <typename T>
struct EdmondsKarp {
    struct Edge { int to; T cap; };
    vector<Edge> edges;
    vector<vector<int>> adj;
    int n;

    EdmondsKarp(int n) : adj(n), n(n) {}

    void addEdge(int u, int v, T cap, T rcap = 0) {
        adj[u].push_back((int)edges.size()); edges.push_back({v, cap});
        adj[v].push_back((int)edges.size()); edges.push_back({u, rcap});
    }

    T maxflow(int s, int t) {
        T flow = 0;
        while (true) {
            vector<int> parEdge(n, -1);
            vector<bool> vis(n, false);
            queue<int> q;
            vis[s] = true; q.push(s);
            while (!q.empty() && !vis[t]) {
                int u = q.front(); q.pop();
                for (int id : adj[u]) {
                    auto &e = edges[id];
                    if (e.cap > 0 && !vis[e.to]) { vis[e.to] = true; parEdge[e.to] = id; q.push(e.to); }
                }
            }
            if (!vis[t]) break;

            T bottleneck = numeric_limits<T>::max();
            for (int v = t; v != s; v = edges[parEdge[v] ^ 1].to) bottleneck = min(bottleneck, edges[parEdge[v]].cap);
            for (int v = t; v != s; v = edges[parEdge[v] ^ 1].to) {
                edges[parEdge[v]].cap -= bottleneck;
                edges[parEdge[v] ^ 1].cap += bottleneck;
            }
            flow += bottleneck;
        }
        return flow;
    }
};