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

Как отправить через сеть как можно больше груза, если у каждого направления есть свой предел? Алгоритм Форда-Фалкерсона строит поток постепенно: находит путь с запасом пропускной способности и увеличивает поток вдоль него. При необходимости он даже отменяет часть прежнего решения. В калькуляторе ниже измените способность одного ребра и посмотрите, когда она перестаёт ограничивать результат.
Что считается потоком
Пусть сеть - ориентированный граф с источником и стоком . Ребро имеет неотрицательную пропускную способность ; поток по нему обозначим . У корректного потока есть два условия:
- на каждом ребре ;
- в каждой промежуточной вершине сумма входящего потока равна сумме исходящего.
Значение потока - это суммарный выход из источника за вычетом входа в него. Его можно представлять как количество единиц груза за час, если все способности заданы в тех же единицах. Задача - найти допустимое распределение с наибольшим значением, а не просто самый широкий отдельный маршрут.
На видео подпись на ребре означает «поток / способность». Золотым выделен путь очередного увеличения; затем показанные состояния идут обратно, чтобы цикл начался с того же кадра. Вершины И и С обозначают источник и сток.
Остаточная сеть и обратное ребро
Предположим, ребро вмещает 7 единиц, а сейчас по нему идут 4. Можно добавить ещё единицы в прямом направлении. Но можно и уменьшить уже отправленные 4 единицы: эту возможность записывают как обратное остаточное ребро способности 4.
Для отдельного исходного ребра остаточные возможности таковы:
Обратная стрелка не означает, что исходная сеть обязательно умеет физически перевозить груз назад. Это разрешение пересмотреть распределение, построенное ранее. Если исходные рёбра есть в обоих направлениях или между вершинами есть параллельные рёбра, храните каждое исходное ребро и его обратное остаточное ребро отдельно: иначе при восстановлении потоков легко перепутать независимые величины.
Дополняющий путь проходит от до по остаточным рёбрам положительной способности. Минимальная способность на пути - бутылочное горлышко . Добавляем на исходных рёбрах, которые путь проходит вперёд, и вычитаем на тех, которые он проходит по обратной остаточной стрелке. На промежуточных вершинах изменение входа и выхода согласовано, поэтому сохранение потока не нарушается.
Разбор сети с отменой решения
Возьмём четыре вершины и пять рёбер:
| Ребро | Способность |
|---|---|
| 3 | |
| 2 | |
| 2 | |
| 2 | |
| 3 |
Начальный поток нулевой. Выберем пути специально так, чтобы увидеть обратное ребро; другой порядок тоже допустим и может дать другие промежуточные состояния.
- Путь имеет остаточные способности 3, 2 и 3. Его минимум равен 2, поэтому отправляем 2 единицы. Значение потока теперь 2.
- Путь имеет остаточные способности 2, 2 и 2. Переход обратен исходному : он уменьшает поток на нём с 2 до 0. После добавления ещё 2 единиц общий поток равен 4.
- Теперь путь снова доступен. Его остаточные способности равны 1, 2 и 1; добавляем 1. Итоговая величина потока - 5.
В результате по рёбрам в порядке таблицы проходят соответственно 3, 2, 1, 2 и 3 единицы. В вершину входят 3 и выходят ; в входят и выходят 3. Все ограничения соблюдены. Без обратной стрелки второй шаг был бы невозможен при выбранном первом пути, хотя более удачное распределение существует.
Как доказать, что 5 - максимум
Разрез делит вершины на две части: источник лежит в , сток - в . Его способность - сумма способностей исходных рёбер, направленных из в . Рёбра в обратном направлении в эту сумму не входят. Любой поток не превосходит способности любого такого разреза: через границу приходится вывести весь чистый поток.
Для нашего примера выберем и . Через границу выходят два ребра способностей 3 и 2, значит способность разреза - 5. Мы уже построили допустимый поток величины 5. Верхняя граница и достигнутое значение совпали: поток максимален, а этот разрез минимален.

Это частный случай теоремы о максимальном потоке и минимальном разрезе. Она также подсказывает способ найти разрез: когда дополняющего пути больше нет, включите в все вершины, достижимые из источника по положительным остаточным рёбрам. Сток окажется вне . Рёбра из наружу насыщены, а поток по исходным рёбрам обратно в равен нулю: иначе соответствующая остаточная стрелка позволила бы достичь ещё одной вершины. Поэтому значение потока совпадает со способностью найденного разреза.
Что показывает изменение одного ребра
Вернёмся к калькулятору в начале статьи. У источника всего два исходящих ребра, их суммарная способность равна 5. Поэтому никакое увеличение внутреннего ребра само по себе не поднимет ответ выше 5: поток не сможет попасть в сеть быстрее, чем это разрешает разрез у источника.
Если же способность перехода из в равна нулю, остаются два независимых маршрута: через проходит не более 2, через тоже не более 2. Их сумма равна 4. При способности перехода 1 недостающая единица может перейти из верхней ветви в нижнюю, и ответ становится равным 5. Дальнейшее увеличение этой способности уже не меняет максимум. В калькуляторе рядом с потоком показаны способности двух разрезов: они служат верхними границами, хотя не каждый из них обязательно минимален.
Такой эксперимент помогает отличить насыщенное ребро от настоящего узкого места всей сети. На некоторых оптимальных распределениях ребро может быть заполнено полностью, но увеличение его способности не улучшит результат: ограничение находится на другом разрезе. Для ответа на вопрос о пользе расширения нужно пересчитать сеть после изменения, а не смотреть лишь на заполнение одного ребра.
Порядок действий и реализация
Метод можно записать независимо от способа поиска пути:
положить все потоки равными нулю
пока в остаточной сети есть путь из s в t:
найти минимум остаточных способностей на пути
увеличить поток вдоль прямых рёбер пути на этот минимум
уменьшить поток вдоль обратных рёбер на тот же минимум
вернуть поток и достижимые из s вершины
На практике удобно хранить для каждого ребра пару записей: прямую и обратную, со ссылками друг на друга. При увеличении на уменьшают остаток первой записи и увеличивают остаток второй. Поиск посещает только рёбра с положительным остатком; массив предков позволяет восстановить путь и вычислить минимум. Перед каждым поиском отметки посещения нужно очистить.
В качестве поиска можно взять обход в глубину или обход в ширину. Для целых способностей оба подходят для общей схемы, но порядок найденных путей влияет на число увеличений и на конкретное распределение. Значение максимума при этом остаётся одинаковым.
Сложность и границы метода
Если способности целые, каждое увеличение при нулевом начальном потоке добавляет хотя бы единицу. При максимальном значении будет не более увеличений; поиск и обновление пути стоят при списках смежности. Получаем оценку , включая последний неудачный поиск. Для связной в нужном смысле сети её часто записывают как при положительном . Это псевдополиномиальная оценка: число может быть велико даже при короткой двоичной записи способностей.
Рациональные способности можно умножить на общий знаменатель и получить целую задачу. Для произвольных вещественных способностей без дополнительного правила выбора пути завершение не гарантировано. Если каждый раз брать кратчайший по числу рёбер остаточный путь, получается алгоритм Эдмондса-Карпа с оценкой , не зависящей от величины потока. Эти свойства и ограничения разобраны в конспекте MIT по сетевым потокам.
Модель применяют к маршрутизации и распределению ресурсов, когда ограничения можно выразить способностями рёбер. Например, задачу о назначениях можно свести к потоку с единичными способностями; близкую идею увеличивающих путей использует алгоритм Куна для паросочетаний. Если важна ещё и стоимость перевозки, одного максимального потока недостаточно: нужна постановка с учётом стоимости.
Частые ошибки
- Искать путь только в исходном графе. Остаточная сеть меняется после каждого увеличения; обратные рёбра могут открыть новый путь.
- Принимать способность за текущий поток. На ребре с записью заняты 2 единицы, а прямой остаток равен 1.
- Увеличивать каждое ребро на его собственный остаток. Вдоль одного пути используют общий минимум, иначе нарушится сохранение в вершинах.
- Считать найденный поток максимальным без проверки. Убедитесь, что остаточного пути нет, либо предъявите разрез той же способности.
FAQ
Обязательно ли выбирать самый широкий путь?
Нет. Общая схема допускает любой путь с положительными остаточными способностями. Стратегия выбора влияет на работу алгоритма, но при завершении отсутствие пути удостоверяет оптимальность.
Может ли максимальных потоков быть несколько?
Да. Их значения совпадают, но потоки на отдельных рёбрах могут различаться. Минимальных разрезов тоже может быть несколько.
Что делать, если источников или стоков несколько?
Можно добавить сверхисточник и соединить его с исходными источниками, а стоки - со сверхстоком. Способности новых рёбер выбирают по ограничениям задачи или достаточно большими, чтобы они искусственно не ограничивали ответ.
Коротко
Форд-Фалкерсон многократно увеличивает поток по остаточному пути на величину его бутылочного горлышка. Обратные рёбра разрешают отменять прежние решения. Когда путь исчез, достижимые из источника вершины задают минимальный разрез: его способность равна найденному максимальному потоку.
Читайте также

Теорема Форда-Фалкерсона о максимальном потоке
Теорема Форда-Фалкерсона связывает максимальный поток и минимальный разрез. Разбираем доказательство через остаточную сеть, пример и проверку решения.

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе
Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

Алгоритм Хирхольцера: как найти эйлеров путь
Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

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

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

Список смежности: представление графа с примерами
Как построить список смежности графа по рёбрам и восстановить граф по спискам. Разбираем ориентированные и взвешенные графы, сложность операций и отличие от матрицы.