Максимальный поток: алгоритм Форда-Фалкерсона простыми словами

Коротко

Задача

Есть сеть труб. У каждой трубы своя пропускная способность. Нужно определить, сколько воды можно прокачать от источника s до стока t за единицу времени.

      10        8
   s ----→ a ----→ t
   |               ↑
 5 |               | 10
   ↓       9       |
   b ----------→ c

Формально: дан ориентированный граф с пропускными способностями рёбер. Поток через каждое ребро не превышает его пропускной способности, а для всех вершин кроме s и t выполняется закон сохранения — сколько втекло, столько и вытекло. Найти максимальную величину потока из s в t.

Применения выходят далеко за трубы: пропускная способность сетей, распределение задач между исполнителями, максимальное паросочетание, сегментация изображений, планирование производства.

Идея: ищем путь и качаем по нему

Базовый алгоритм на удивление прост.

1. Найти любой путь из s в t, где по всем рёбрам ещё есть запас.
2. Прокачать по нему столько, сколько позволяет самое узкое ребро.
3. Уменьшить остаточные пропускные способности вдоль пути.
4. Повторять, пока такие пути находятся.

Такой путь называется дополняющим. Когда их больше нет, поток максимален.

Ключевая тонкость: обратные рёбра

Наивная реализация даёт неверный ответ, и вот почему.

Представьте, что мы жадно прокачали поток по неудачному маршруту и «заблокировали» ребро, которое было нужнее другому пути. Алгоритм должен уметь отменить часть своего решения.

Решение элегантное: при прокачке f единиц по ребру u → v мы не только уменьшаем его остаток на f, но и увеличиваем на f остаток обратного ребра v → u.

было:   u --10--→ v         обратное: v --0--→ u
качаем 6 единиц
стало:  u --4--→ v          обратное: v --6--→ u

Теперь если алгоритм пойдёт по v → u, это будет означать «верни 6 единиц обратно, они пригодятся в другом месте». Обратные рёбра — механизм отката, без которого алгоритм не находит оптимум.

Теорема о максимальном потоке и минимальном разрезе

Красивейший результат в этой области.

Разрез — разбиение вершин на две группы: одна содержит s, другая t. Пропускная способность разреза — сумма пропускных способностей рёбер, идущих из первой группы во вторую.

Теорема: величина максимального потока равна пропускной способности минимального разреза.

Интуиция: поток не может превысить любой разрез, потому что вся вода обязана через него пройти. А минимальный разрез — самое узкое место сети, и оно и определяет пропускную способность.

Практическая польза: решив задачу о потоке, вы бесплатно получаете ответ на задачу о минимальном разрезе. Вершины, достижимые из s в остаточной сети после работы алгоритма, образуют одну сторону минимального разреза.

Реализация: алгоритм Эдмондса-Карпа

Форд-Фалкерсон не уточняет, как искать дополняющий путь. Если искать в глубину, на неудачных данных алгоритм может работать очень долго. Эдмондс и Карп предложили искать в ширину — то есть брать кратчайший по числу рёбер путь. Это даёт гарантию O(V·E²) независимо от величин пропускных способностей.

from collections import deque


def edmonds_karp(capacity: dict, source, sink) -> int:
    """capacity: {(u, v): пропускная способность}. Возвращает величину потока."""
    # строим списки смежности, включая обратные рёбра
    adj = {}
    residual = {}
    for (u, v), c in capacity.items():
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)   # обратное ребро тоже сосед
        residual[(u, v)] = c
        residual.setdefault((v, u), 0)    # обратное с нулевым остатком

    max_flow = 0

    while True:
        # BFS ищет кратчайший дополняющий путь
        parent = {source: None}
        queue = deque([source])

        while queue and sink not in parent:
            u = queue.popleft()
            for v in adj.get(u, ()):
                if v not in parent and residual.get((u, v), 0) > 0:
                    parent[v] = u
                    queue.append(v)

        if sink not in parent:
            break          # дополняющих путей больше нет

        # находим узкое место на пути
        bottleneck = float('inf')
        v = sink
        while parent[v] is not None:
            u = parent[v]
            bottleneck = min(bottleneck, residual[(u, v)])
            v = u

        # прокачиваем поток и обновляем остаточную сеть
        v = sink
        while parent[v] is not None:
            u = parent[v]
            residual[(u, v)] -= bottleneck
            residual[(v, u)] += bottleneck     # обратное ребро растёт
            v = u

        max_flow += bottleneck

    return max_flow


capacity = {
    ('s', 'a'): 10,
    ('s', 'b'): 5,
    ('a', 't'): 8,
    ('b', 'c'): 9,
    ('c', 't'): 10,
    ('a', 'c'): 2,
}

print(edmonds_karp(capacity, 's', 't'))   # 13

Разберём ответ: 8 единиц уходит по маршруту s → a → t, ещё 5 по s → b → c → t. Больше не получится — из истока выходит всего 15, но a → t ограничивает первую ветку восемью.

Максимальное паросочетание через поток

Самое частое применение в олимпиадных задачах. Двудольный граф превращается в сеть:

• добавляем исток s, соединяем его со всеми вершинами левой доли рёбрами пропускной способности 1;
• добавляем сток t, соединяем с ним все вершины правой доли, тоже по 1;
• исходные рёбра между долями получают пропускную способность 1.

Максимальный поток в такой сети равен размеру максимального паросочетания. Единичные пропускные способности гарантируют, что каждая вершина участвует не более чем в одной паре.

def max_matching(left: list, right: list, edges: list[tuple]) -> int:
    capacity = {}
    for u in left:
        capacity[('__s', u)] = 1
    for v in right:
        capacity[(v, '__t')] = 1
    for u, v in edges:
        capacity[(u, v)] = 1

    return edmonds_karp(capacity, '__s', '__t')


print(max_matching(
    ['a', 'b', 'c'],
    ['x', 'y', 'z'],
    [('a', 'x'), ('a', 'y'), ('b', 'y'), ('c', 'z')]
))   # 3

Другие применения

Минимальный разрез — по теореме получается автоматически. Используется в компьютерном зрении для сегментации изображений (алгоритм graph cut).

Распределение ресурсов: назначить работников на задачи с учётом ограничений по количеству.

Планирование расписаний с ограничениями по времени и вместимости.

Анализ надёжности сети: минимальный разрез показывает, сколько связей нужно разорвать для отключения потребителя.

Задача о циркуляции с нижними границами — обобщение, решающее целый класс задач планирования.

Почему нужен именно BFS

Показательный пример: граф из четырёх вершин, где два «толстых» ребра по 1000 соединены «тонким» ребром пропускной способности 1.

Поиск в глубину может каждый раз выбирать путь через тонкое ребро, прокачивая по одной единице за итерацию, — потребуется 2000 итераций. Поиск в ширину найдёт короткие пути и справится за две.

Именно поэтому оценка Форда-Фалкерсона содержит величину потока f, а у Эдмондса-Карпа её нет.

Частые ошибки

Отсутствие обратных рёбер. Алгоритм выдаст какой-то поток, но не максимальный. Ошибка не падает, а тихо портит ответ.

Поиск в глубину вместо ширины. На плохих данных приводит к таймауту.

Забытая инициализация обратного ребра нулём. residual.setdefault((v, u), 0) — если этого нет, обращение к несуществующему ключу упадёт.

Использование потока вместо остатка при BFS. Проходить можно только по рёбрам с положительным остатком, а не с положительной пропускной способностью.

Что запомнить

• Максимальный поток находится многократным поиском дополняющих путей.
• Обратные рёбра обязательны — они позволяют алгоритму откатывать неудачные решения.
• Величина максимального потока равна пропускной способности минимального разреза.
• Эдмондс-Карп это Форд-Фалкерсон с поиском в ширину и гарантией O(V·E²).
• Задача о максимальном паросочетании сводится к потоку с единичными пропускными способностями.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→