Алгоритм Форда-Фалкерсона

Код

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;

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

    bool hasPath(int start, int finish) {
        visited.assign(graph.size(), 0);
        edgeTo.assign(graph.size(), -1);
        dfs(start);
        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;
    }
};

Сложность

Один запуск hasPath() выполняется за O(V + E), getMinCapacity() и addFlow() — за O(V).

Если пропускные способности целочисленные, то после одной итерации поиска увеличивающего пути в худшем случае поток увеличится на 1. Таким образом, в худшем случае потребуется Flow итераций.

Пример графа с V = 50, E = 97, F = 2^24:

int constructGraph(Graph &graph, int start, int finish) {
    if (start + 1 == finish) {
        graph.addEdge(start, finish, 1);
        return 1;
    }

    int capacity = constructGraph(graph, start + 1, finish - 1);
    graph.addEdge(start, start + 1, capacity);
    graph.addEdge(start, finish - 1, capacity);
    graph.addEdge(start + 1, finish, capacity);
    graph.addEdge(finish - 1, finish, capacity);
    return capacity * 2;
}

int main() {
    int vertexCount = 50;
    Graph graph(vertexCount);
    constructGraph(graph, 0, vertexCount - 1);
    cout << graph.maxFlow(0, vertexCount - 1);
}

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

Ссылки

Теория:

• algs4.cs.princeton.edu — 6.4 Maximum Flow
• neerc.ifmo.ru/wiki — Алгоритм Форда-Фалкерсона
• Brilliant.org — Ford-Fulkerson Algorithm
• codeforces.com — Worst-Case Graphs for Maximum Flow Algorithms

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

• VisuAlgo — Network Flow

Код:

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

Задачи:

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