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

Алгоритм Эдмондса-Карпа - это реализация общей схемы Форда-Фалкерсона для задачи о максимальном потоке, в которой дополняющий путь от источника к стоку ищется обычным BFS, а не произвольным DFS. Один-единственный технический выбор - «поиск в ширину вместо поиска в глубину» - превращает алгоритм, который в худшем случае может работать сколь угодно долго (а при иррациональных пропускных способностях вообще не сходится), в строго полиномиальный $O(V \cdot E^2)$. Назван по статье Джека Эдмондса и Ричарда Карпа 1972 года, хотя ту же идею в 1970-м опубликовал и Е. А. Диниц.

Задача о максимальном потоке - постановка

Дан ориентированный граф $G = (V, E)$ с двумя выделенными вершинами - источником $s$ и стоком $t$. Каждому ребру $(u, v)$ приписана пропускная способность $c(u, v) \ge 0$. Потоком называется функция $f \colon E \to \mathbb{R}_{\ge 0}$, удовлетворяющая:

1. Ограничение пропускной способности: $0 \le f(u, v) \le c(u, v)$ для всех рёбер.
2. Сохранение потока: для любой $v \ne s, t$ суммарный входящий поток равен суммарному исходящему.

Величина потока - $|f| = \sum_{v} f(s, v) - \sum_{v} f(v, s)$, то есть нетто-исток из источника. Задача - найти $f$ с максимальным $|f|$.

Общая схема Форда-Фалкерсона

Идея, лежащая в основе всех классических алгоритмов потока, - остаточная сеть $G_f$. У каждого ребра $(u, v)$ в остаточной сети две стороны:

• Прямая остаточная способность $c_f(u, v) = c(u, v) - f(u, v)$ - сколько ещё можно пропустить в направлении $u \to v$.
• Обратная остаточная способность $c_f(v, u) = f(u, v)$ - сколько потока можно «откатить», уменьшив текущий $f(u, v)$.

Дополняющий путь (augmenting path) - путь из $s$ в $t$ по рёбрам с $c_f > 0$. Минимум остаточных способностей вдоль пути - его «бутылочное горлышко» $\Delta$; на этот $\Delta$ потоки прямых рёбер пути увеличиваются, обратных - уменьшаются.

while существует augmenting path s → t в G_f:
    Δ = min{c_f(u, v) : (u, v) на пути}
    обновить f вдоль пути на Δ
return f

Теорема Форда-Фалкерсона (1956): процесс заканчивается тогда и только тогда, когда дополняющего пути в $G_f$ больше нет, и в этот момент $|f|$ равно пропускной способности минимального $s$-$t$-разреза. Это и есть теорема о максимальном потоке и минимальном разрезе.

Открытый вопрос - как именно искать дополняющий путь. Если выбирать произвольно, поведение зависит от пропускных способностей. На целых $c$ алгоритм закончится за конечное число шагов (поток растёт на целое число), но число шагов может быть пропорционально значению потока $|f|^*$ - то есть псевдополиномиальным. Хуже того, на иррациональных пропускных способностях существуют примеры (классическая конструкция Цвика 1995 г. на 6 вершинах с $\varphi = (\sqrt{5} - 1)/2$), где Форд-Фалкерсон не только медленно работает, но и не сходится - стремится к величине, меньшей максимума.

Главная идея Эдмондса-Карпа - BFS вместо DFS

Эдмондс и Карп в 1972 году заметили: если выбирать дополняющий путь кратчайший по числу рёбер (а не первый попавшийся DFS), число итераций ограничено $O(V \cdot E)$ независимо от пропускных способностей - даже для иррациональных. А кратчайший путь в графе с единичными весами рёбер находится обычным BFS из источника.

Псевдокод:

function edmonds_karp(G, s, t):
    f(u, v) = 0 для всех (u, v) ∈ E
    while True:
        # BFS в остаточной сети
        prev = массив предков, prev[s] = s, остальные null
        очередь = [s]
        пока очередь не пуста и prev[t] == null:
            u = pop(очередь)
            для каждой (u, v) с c_f(u, v) > 0 и prev[v] == null:
                prev[v] = u
                push(очередь, v)
        если prev[t] == null:
            return f                  # пути нет - поток максимален
        # восстановление пути и его бутылочного горлышка
        Δ = ∞
        v = t
        пока v ≠ s:
            Δ = min(Δ, c_f(prev[v], v))
            v = prev[v]
        # обновление потока вдоль пути
        v = t
        пока v ≠ s:
            f(prev[v], v) += Δ
            f(v, prev[v]) -= Δ
            v = prev[v]

Никаких эвристик; никаких приоритетных очередей; никакого выбора «бутылочного горлышка» - только BFS, бесхитростный и одинаковый.

Доказательство $O(V \cdot E^2)$

Ключевая лемма Эдмондса-Карпа звучит так.

Лемма (монотонность кратчайших расстояний). Пусть $\delta_f(s, v)$ - расстояние от $s$ до $v$ в остаточной сети $G_f$ (число рёбер). На протяжении работы алгоритма $\delta_f(s, v)$ не убывает по $v$ ни для одной вершины.

Доказательство - от противного: если расстояние уменьшилось после очередной аугментации, рассматривается «возникшее» ребро в остаточной сети, и через индукцию по $\delta$ получается противоречие с тем, что мы шли по кратчайшему пути.

Следствие. Назовём ребро $(u, v)$ критическим на конкретной итерации, если $c_f(u, v)$ - минимум вдоль найденного пути (то есть оно «перегорает» при текущей аугментации, $\Delta = c_f(u, v)$). Сколько раз каждое ребро может оказаться критическим?

После того, как $(u, v)$ стало критическим, оно исчезает из остаточной сети. Чтобы оно вернулось, в каком-то будущем кратчайшем пути должно появиться обратное ребро $(v, u)$ - а оно возникает только тогда, когда поток вдоль $(u, v)$ начнут отменять, то есть когда $u$ снова окажется на кратчайшем пути уже после $v$. В этот момент $\delta(s, u) \ge \delta(s, v) + 1$. С учётом монотонности и того, что $\delta(s, u) \le V - 1$, каждое ребро может стать критическим не более $V / 2$ раз.

Каждая аугментация имеет хотя бы одно критическое ребро. Всего рёбер $E$ (с учётом обратных - $2E$), значит число итераций - $O(V \cdot E)$. Одна итерация - это BFS на $O(E)$. Итого:

$T_{EK} = O(V \cdot E) \cdot O(E) = O(V \cdot E^2).$

Подчёркиваем: оценка не зависит от пропускных способностей. Даже на иррациональных $c$, на которых обычный Форд-Фалкерсон не сходится, Эдмондс-Карп закончит работу за полиномиальное число шагов.

Связь с теоремой о максимальном потоке и минимальном разрезе

В момент, когда BFS из $s$ не достигает $t$, помеченные вершины $S$ - те, до которых ещё «можно дойти» в $G_f$, - образуют одну сторону разреза, $T = V \setminus S$ - вторую. Все рёбра $(u, v)$ с $u \in S, v \in T$ исходного графа насыщены ($f = c$), все обратные имеют $f = 0$. Сумма пропускных способностей этих рёбер - это и есть пропускная способность минимального разреза, и она равна $|f|$. Таким образом, прогон Эдмондса-Карпа автоматически даёт и максимальный поток, и явный минимальный разрез - без дополнительной работы.

Применения

• Двудольное паросочетание. Задача сводится к потоку: источник $s$ соединяют рёбрами единичной пропускной способности со всеми вершинами левой доли, сток $t$ - с правыми, исходные рёбра делают единичными. Размер максимального паросочетания равен максимальному потоку; на таком графе Эдмондс-Карп даёт $O(V \cdot E)$ - те же гарантии, что у алгоритма Куна.
• Задача о назначении в невзвешенной форме; во взвешенной - нужен min-cost flow с похожей BFS-структурой.
• Image segmentation. Алгоритм GrabCut строит graph cut, в котором min cut между двумя терминалами разделяет пиксели на «фон» и «объект». Эдмондс-Карп - простая реализация, в практике обычно заменяют на Boykov-Kolmogorov.
• Сетевая надёжность (vertex/edge connectivity), задачи о размещении, маршрутизация - везде, где постановка укладывается в network flow.

Сравнение с другими алгоритмами max-flow

Алгоритм Диница работает с той же остаточной сетью, но за одну BFS-фазу строит слоистую сеть (уровни - расстояние от $s$) и насыщает в ней сразу блокирующий поток - максимальный поток в слоистой сети целиком. Число фаз $O(V)$, фаза $O(V \cdot E)$, итого $O(V^2 E)$. На единичных пропускных способностях Диниц даёт $O(E \sqrt{V})$ - это и есть алгоритм Хопкрофта-Карпа для двудольного паросочетания. Push-Relabel идёт совсем другим путём, проталкивая избыток по высотам, и в реализации с highest-label достигает $O(V^2 \sqrt{E})$.

Для учебных задач и графов до пары тысяч вершин - Эдмондс-Карп. Простой, корректный, легко проверяемый. Для production - Диниц или Boykov-Kolmogorov.

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

• Используют DFS вместо BFS. Это уже не Эдмондс-Карп, а обычный Форд-Фалкерсон без гарантий времени. На иррациональных пропускных способностях такая реализация не сойдётся; на больших целых - будет работать пропорционально $|f|^*$, а не $V \cdot E^2$.
• Забывают про обратные рёбра. Каждое ребро $(u, v)$ в остаточной сети - это два «полуребра»: прямое с $c_f = c - f$ и обратное с $c_f = f$. Без обратных нельзя «откатить» неудачную аугментацию, и алгоритм найдёт не максимальный, а только некоторый локально-максимальный поток.
• Считают расстояние BFS по весам пропускных способностей. В BFS веса игнорируются - кратчайший в Эдмондсе-Карпе значит «по числу рёбер». Если случайно использовать Дейкстру с весами $c$, лемма о монотонности перестаёт работать.
• Запускают на неориентированном графе как есть. Неориентированное ребро $\{u, v\}$ с пропускной способностью $c$ обычно моделируют двумя независимыми ориентированными с тем же $c$ - это даёт правильный ответ, потому что оптимальный поток не пойдёт одновременно в обе стороны.

FAQ

Чем алгоритм Эдмондса-Карпа отличается от алгоритма Форда-Фалкерсона? Это та же самая схема, но с зафиксированной стратегией выбора дополняющего пути - BFS. Форд-Фалкерсон в исходной формулировке ничего про выбор пути не говорит; Эдмондс-Карп - это конкретная реализация, и именно она даёт строго полиномиальную сложность $O(V \cdot E^2)$.

Почему BFS гарантирует полиномиальное время, а DFS - нет? Из-за леммы о монотонности кратчайших расстояний в остаточной сети. При BFS-выборе аугментирующего пути $\delta_f(s, v)$ не убывает, и каждое ребро может стать критическим лишь $O(V)$ раз. При DFS такой инвариант не выполняется: кратчайшие расстояния могут «прыгать», и число итераций перестаёт ограничиваться полиномом от $V$ и $E$.

Можно ли запускать Эдмондса-Карпа на графе с дробными или иррациональными пропускными способностями? Да, и в этом одно из главных его преимуществ. Анализ через критические рёбра не использует целочисленность, поэтому $O(V \cdot E^2)$ итераций гарантировано при любых $c \ge 0$. Это контрастирует с обычным Фордом-Фалкерсоном, где плохой выбор пути на иррациональных $c$ может привести к несходящемуся процессу.

Коротко

Алгоритм Эдмондса-Карпа - это Форд-Фалкерсон с фиксированной стратегией: дополняющий путь ищется кратчайший по числу рёбер, то есть обычным BFS из источника в остаточной сети. Эта мелочь даёт строго полиномиальную сложность $O(V \cdot E^2)$ и снимает зависимость от пропускных способностей - алгоритм одинаково корректно работает на целых, дробных и иррациональных $c$. Доказательство опирается на лемму о монотонности кратчайших расстояний и подсчёт того, сколько раз ребро может стать критическим - $O(V)$ раз каждое. Эдмондс-Карп решает задачи о максимальном потоке, минимальном разрезе, двудольном паросочетании (через стандартное сведение), назначении и сегментации изображений. Когда нужны лучшие константы - берут Диница $O(V^2 E)$ или Push-Relabel $O(V^2 \sqrt{E})$, но для учебных и средних задач Эдмондс-Карп остаётся базовым выбором.