Алгоритм Эдмондса-Карпа

Код

class Graph {
    struct Edge {
        int a, b, capacity, flow = 0;

        Edge(int a, int b, int capacity) :
            a(a), b(b), capacity(capacity) {}

        int other(int v) const {
            return v == b ? a : b;
        }

        int capacityTo(int v) const {
            return v == b ? capacity - flow : flow;
        }

        void addFlowTo(int v, int deltaFlow) {
            flow += (v == b ? deltaFlow : -deltaFlow);
        }
    };

    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<int> visited, edgeTo;

    bool hasPath(int start, int finish) {
        visited.assign(graph.size(), 0);
        edgeTo.assign(graph.size(), -1);
        queue<int> q;

        visited[start] = 1;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int edgeIndex : graph[v]) {
                int to = edges[edgeIndex].other(v);
                if (!visited[to] && edges[edgeIndex].capacityTo(to)) {
                    visited[to] = 1;
                    edgeTo[to] = edgeIndex;
                    q.push(to);
                }
            }
        }

        return visited[finish];
    }

    int getMinCapacity(int start, int finish) {
        int minCapacity = 1e9;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
        return minCapacity;
    }

    void addFlow(int start, int finish, int deltaFlow) {
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            edges[edgeTo[v]].addFlowTo(v, deltaFlow);
    }

public:
    Graph(int vertexCount) : graph(vertexCount) {}

    void addEdge(int from, int to, int capacity) {
        edges.push_back(Edge(from, to, capacity));
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }

    long long maxFlow(int start, int finish) {
        long long flow = 0;
        while (hasPath(start, finish)) {
            int deltaFlow = getMinCapacity(start, finish);
            addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return flow;
    }
};

Сложность

• Факт 1. Пусть в BFS мы бы считали расстояния до каждой вершины. Тогда при последовательных запусках BFS эти расстояния никогда не уменьшались бы.

Пусть BFS нашёл путь start → a → b → c → d → finish. Сейчас dist[start] = 0, dist[a] = 1, dist[b] = 2, ... dist[finish] = 5.

Утверждается, что и при следующих запусках BFS эти расстояния не смогут стать меньше. Когда мы добавим поток вдоль этого пути:

• По каким-то рёбрам станет невозможно ходить слева направо, это не может улучшить расстояния.
• По каким-то рёбрам станет можно ходить справа налево, но это тоже не может улучшить расстояния:

Пусть стал доступен переход b ← c, следующий BFS прошёл по нему, и b — первая вершина на новом кратчайшем пути, до которой расстояние уменьшилось.

Но oldDist[c] = oldDist[b] + 1, newDist[c] >= oldDist[c], newDist[b] = newDist[c] + 1. Тогда newDist[b] >= oldDist[b] + 2, расстояние до b не могло уменьшиться, противоречие.

• Расстояние до какой-то вершины могло стать меньше, только если до этой вершины существовал более короткий путь. Тогда BFS должен был найти именно его, противоречие.

• Факт 2. После каждой итерации хотя бы одно ребро насыщается потоком в ту или в другую сторону, при этом его остаточная пропускная способность становится равной нулю.

Прежде чем это ребро станет можно использовать снова в том же направлении, поток должен пройти по нему в обратном направлении.

Как было показано выше, при этом расстояние до его начала увеличится как минимум на 2 (newDist[b] >= oldDist[b] + 2).

• Факт 3. Расстояния, очевидно, не могут превышать (V - 1).

Получается, что каждое ребро может быть насыщено потоком не более (V - 1) раз (по (V - 1) / 2 раз в ту и в другую сторону). Разных рёбер E штук, следовательно, суммарное количество запусков BFS не может превосходить ((V - 1) × E). Один запуск стоит O(V + E).

Общая сложность, таким образом, составляет O(((V - 1) × E) × (V + E)) = O(V × E^2) в худшем случае.

Ссылки

Теория:

• algs4.cs.princeton.edu — 6.4 Maximum Flow
• e-maxx.ru — Алгоритм Эдмондса-Карпа нахождения максимального потока за O (NM^2)
• neerc.ifmo.ru/wiki — Алгоритм Эдмондса-Карпа
• Brilliant.org — Edmonds-Karp Algorithm
• codeforces.com — Worst-Case Graphs for Maximum Flow Algorithms

Демонстрация:

• VisuAlgo — Network Flow

Код:

• CodeLibrary — Maximum flow. Edmonds-Karp algorithm in O(min(E^2 * V, E * FLOW))
• algs4.cs.princeton.edu/code — capacitated edge with flow, capacitated network, maxflow–mincut (несмотря на название, используется алгоритм Эдмондса-Карпа)

Задачи:

• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 9
• Задачи: Максимальный поток