Алгоритм Форда-Фалкерсона: Поиск максимального потока в сети
Одной из классических задач дискретной оптимизации на графах является задача о максимальном потоке. Представьте сеть трубопроводов разного диаметра, систему городских автомобильных дорог с разной пропускной способностью или компьютерную сеть маршрутизаторов. Как пропустить максимальный объем жидкости, машин или гигабайт данных от источника к потребителю так, чтобы ни на одном участке не превысить лимит? Ответом на этот вопрос является знаменитый алгоритм Форда-Фалкерсона.
Математическая модель транспортной сети — это ориентированный граф, в котором каждому ребру приписано неотрицательное число — его пропускная способность (Capacity). Выделяются две особые вершины: Исток (Source, S), генерирующий поток, и Сток (Sink, T), поглощающий его. Для всех остальных промежуточных узлов действует закон сохранения: сколько потока втекает в вершину, ровно столько же должно из нее вытекать.
Алгоритм Форда-Фалкерсона работает итеративно и базируется на гениальной концепции остаточной сети (Residual Graph). Суть метода заключается в следующем:
- Изначально поток по всем ребрам равен нулю.
- Алгоритм пытается найти любой путь от Истока к Стоку в остаточной сети (используя обычный DFS или BFS), вдоль которого можно пропустить хотя бы еще немного потока. Такой путь называется увеличивающим путем (Augmenting path).
- Алгоритм находит "бутылочное горлышко" этого пути — ребро с минимальной остаточной пропускной способностью. На это значение увеличивается суммарный поток.
- Ключевой математический трюк: чтобы алгоритм не загнал себя в тупик ошибочным жадным решением на ранних этапах, в остаточной сети добавляются обратные ребра. Это позволяет алгоритму виртуально "отменить" ранее пущенный неудачный поток, пустив новый поток ему навстречу.
- Шаги повторяются, пока в остаточной сети можно найти хотя бы один увеличивающий путь. Когда таких путей не остается — найденный поток математически гарантированно является максимальным.
Корректность алгоритма опирается на фундаментальную теорему Форда-Фалкерсона о максимальном потоке и минимальном разрезе (Max-flow min-cut theorem). Она гласит, что максимальное количество потока от S к T в точности равно суммарной пропускной способности самого "узкого" места сети (минимального разреза графа, разделяющего S и T).
В оригинальном виде метод Форда-Фалкерсона не регламентирует, как именно искать увеличивающий путь. Если пропускные способности иррациональны, алгоритм может вообще никогда не завершиться. Эту проблему решили Эдмондс и Карп, предложив всегда искать кратчайший (по числу ребер) увеличивающий путь с помощью поиска в ширину (BFS). Алгоритм Эдмондса-Карпа строго гарантирует завершение работы за полиномиальное время O(V * E^2).
