Все формулы РФ

Информатика / Алгоритмы и анализ данных

Алгоритм Эдмондса—Карпа: поток с поиском в ширину

Алгоритм Эдмондса—Карпа выбирает увеличивающий путь с минимальным числом остаточных дуг при помощи BFS. Эта стратегия превращает общий метод увеличения потока в алгоритм с оценкой времени O(VE²).

Опубликовано: Обновлено:

Анализ данныхАлгоритмы и анализ данныхСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$P=\operatorname{BFS}(G_f,s,t),\quad\delta=\min_{e\in P}c_f(e),\quad T=O(VE^2)$$
Схема BFS: два пути длины 2, затем длины 3
BFS: два пути длины 2, затем длины 3BFS: два пути длины 2, затем длины 332123sabt

Подписи — исходные ёмкости. Сначала s→a→t и s→b→t; последним используется a→b.

Обозначения

$Gf$
текущая остаточная сеть, граф
$V,E$
числа вершин и исходных дуг, 1
$P$
кратчайший по числу дуг остаточный путь, путь
$cf,δ$
остаточная ёмкость и увеличение, единица потока

Условия применения

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

Ограничения

BFS не выбирает путь максимальной пропускной способности и не использует сумму ёмкостей как расстояние. O(VE²) может быть медленно на большой плотной сети. Вычисления с плавающей точкой требуют допуска для остаточных значений, иначе возникает численный шум.

Подробное объяснение

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

Расстояния от источника в остаточной сети не уменьшаются по мере увеличений. Когда одна дуга повторно становится критической, её положение относительно слоёв BFS должно продвинуться. Это ограничивает число критических насыщений каждой дуги величиной порядка V.

Всего увеличений получается O(VE). Одно построение BFS и обновление пути стоят O(E) при списках смежности, поэтому время O(VE²). Эта аргументация относится к стратегии выбора путей и не использует верхнюю границу |f*| для числа шагов.

Как и у общего метода, обратные остаточные дуги нужны для перенаправления. Отсутствие пути даёт разрез максимальности. Эдмондс—Карп улучшает гарантию вычислений, но не меняет ограничения допустимого потока или смысл итогового сертификата.

Как пользоваться формулой

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

Историческая справка

Вариант Эдмондса—Карпа уточняет общий метод Форда—Фалкерсона строгим правилом выбора пути. Поиск в ширину связывает последовательность увеличений со слоями остаточной сети, благодаря чему число шагов ограничивается структурой графа, а не величинами ёмкостей.

В алгоритмической практике XX–XXI веков такой анализ стал характерным примером перехода от корректного метода к полиномиально ограниченному алгоритму. Princeton описывает реализацию FordFulkerson с кратчайшим увеличивающим путём и временем E²V. Современные учебные разборы отдельно объясняют монотонность расстояний и повторные насыщения дуг. Название Эдмондса—Карпа поэтому относится к BFS-стратегии внутри остаточного метода, а не к другой постановке задачи потока.

Историческая линия формулы

Алгоритм Эдмондса—Карпа — вариант увеличивающих путей с поиском в ширину. Его отличительный результат — оценка O(VE²), основанная на слоях остаточной сети. Реализация Princeton использует эту стратегию внутри класса с названием FordFulkerson.

Пример

Дуги сети: s→a=3, s→b=2, a→b=1, a→t=2, b→t=3. При обходе a перед b первый кратчайший путь s→a→t имеет две дуги и допускает 2. Второй BFS находит s→b→t и добавляет 2. Теперь прямые двухдуговые пути исчерпаны, но остаётся s→a→b→t с ёмкостями 1,1,1; добавляем ещё 1. Общий поток 5. Его распределение: s→a=3, s→b=2, a→t=2, a→b=1, b→t=3. Баланс в a: 3=2+1; в b: 2+1=3. Разрез {s} имеет ёмкость 3+2=5, значит результат максимален. BFS выбирал число дуг, а не наибольшую сумму их ёмкостей. Все пять дуг соблюдают свои исходные ограничения.

Частая ошибка

После каждого увеличения отметки BFS и предки строятся заново. Нельзя взвешивать расстояние ёмкостями и продолжать называть поиск BFS. Обратные дуги не удаляются из рассмотрения. Оценка O(VE²) не означает, что каждый конкретный пример должен выполнить ровно VE увеличений.

Практика

Задачи с решением

Выбор BFS

Условие. Есть пути s→t с ёмкостью 1 и s→a→t с ёмкостями 10,10. Какой выберет BFS первым?

Решение. Путь s→t имеет одну дугу вместо двух, независимо от меньшей ёмкости.

Ответ. s→t; увеличение 1.

Баланс вершины

Условие. После шага в a входят 5, выходят к b 2 и к t 3. Допустим ли баланс?

Решение. Вход 5 равен выходу 2+3=5; внутреннего накопления нет.

Ответ. Да, баланс выполнен.

Дополнительные источники

  • https://algs4.cs.princeton.edu/64maxflow/
  • https://cp-algorithms.com/graph/edmonds_karp.html

Связанные формулы

Информатика

Метод Форда—Фалкерсона: увеличивающий путь потока

$\delta=\min_{e\in P}c_f(e),\quad |f_{\mathrm{new}}|=|f|+\delta,\quad c_f(u,v)=c(u,v)-f(u,v)$

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

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.

Информатика

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

$\max_f |f|=\min_{s\in S,\ t\notin S}c(S,V\setminus S),\quad c(S,\bar S)=\sum_{u\in S,\ v\notin S}c(u,v)$

Теорема о максимальном потоке и минимальном разрезе даёт сертификат оптимальности: допустимый поток максимален, если его величина совпала с суммой ёмкостей некоторого разделяющего разреза источника и стока.