Алгоритм Форда-Фалкерсона: пошаговое объяснение и примеры для максимального потока

hannadev

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

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

Что такое остаточная сеть и зачем она нужна

Остаточная сеть — это ключевой элемент алгоритма Форда-Фалкерсона. Она строится на основе исходного графа и текущего потока, показывая, сколько еще можно пропустить по каждому ребру. Для ребра от u к v остаточная пропускная способность считается как c(u,v) - f(u,v), где c — исходная емкость, f — текущий поток. Если поток уже максимален, там добавляются обратные ребра с возможностью “вернуть” поток.

Представьте транспортную сеть: дороги с ограничениями по грузоподъемности. На каждой итерации алгоритм смотрит, можно ли усилить поток, не ломая правила. Это позволяет корректировать маршруты, даже уменьшая поток по некоторым ребрам для общего роста. Без остаточной сети метод не смог бы найти оптимальный путь.

Инициализация: Все потоки f(u,v) = 0, остаточная сеть совпадает с исходной.
Поиск пути: Ищем путь от источника s к стоку t в остаточной сети с помощью BFS или DFS.
Обновление: Находим минимальную остаточную емкость cf_min по пути и корректируем потоки: прямые ребра увеличиваем, обратные — уменьшаем.

Шаг	Действие	Изменение в сети
1	Инициализация	f=0, Gf = G
2	Поиск пути p	cf_min > 0
3	Обновление f	f += cf_min по p

Важно: Обратные ребра позволяют “откатывать” поток, если это выгодно для максимума.

Как работает поиск увеличивающего пути

Увеличивающий путь — это маршрут от s к t в остаточной сети, где по всем ребрам остаточная емкость положительна. Алгоритм повторяет поиск таких путей, пока они существуют. Каждый раз поток растет как минимум на 1, если емкости целые, что гарантирует конечность.

Возьмем пример сети: s → a (10), s → b (10), a → t (10), b → t (10), a → b (2). Сначала найдем путь s-a-t с cf_min=10, поток станет 10. Остаточная сеть обновится: s-a (0), a-t (0), но появится t-a (10). Далее путь s-b-a-t с cf_min=2 (через обратное ребро), итоговый поток 12.

Используйте DFS или BFS для поиска пути — время O(E) на итерацию.
Вычисляйте cf_min = min{cf(u,v) по пути}.
После обновления проверяйте, есть ли еще пути.

Вот таблица изменений для примера:

Итерация	Путь	cf_min	Общий поток
1	s-a-t	10	10
2	s-b-a-t	2	12
3	Нет пути	-	Максимум 12

Преимущество: Метод универсален, работает с любыми емкостями, но зависит от выбора поиска пути.

Пошаговый алгоритм и пример реализации

Псевдокод прост: while есть путь p в Gf, проталкиваем cf_min и обновляем сеть. Инициализация — нулевой поток. Цикл продолжается до отсутствия пути от s к t. Сложность O(|V||E|^2) в худшем случае, но с BFS (Эдмондс-Карп) — O(|V||E|^2).

Рассмотрим сеть с вершинами s, 1, 2, t. Ребра: s-1(4), s-2(3), 1-2(2), 1-t(3), 2-t(5). Итерация 1: s-1-t, cf_min=3, поток=3. Итерация 2: s-2-t, cf_min=3, поток=6. Итерация 3: s-1-2-t, cf_min=1 (1-2 остаток 2, но мин с другими), поток=7. Дальше пути нет.

FordFulkerson(G, s, t):
1. f = 0 для всех ребер.
2. Пока существует p от s к t в Gf:
  - cf_p = min по p.
  - Для каждого ребра в p: f(u,v) += cf_p, f(v,u) -= cf_p.
Нюанс: Ребра с нулевой емкостью удаляются из Gf.
В Python: используйте словари для графа, BFS с parent-массивом.

Ребра	Исходная c	После итераций f
s-1	4	4
1-t	3	3
2-t	5	4

Метод доказуемо находит максимум по теореме о максимальном потоке и минимальном разрезе.

Практические применения и ограничения метода

Алгоритм Форда-Фалкерсона применяется в логистике для распределения грузов, в телекоме для маршрутизации трафика, в производстве для оптимизации цепочек поставок. Он масштабируется на большие графы с улучшениями вроде Dinic или Preflow-push.

В реальных задачах сети могут иметь тысячи вершин, так что чистый метод медленный при плохом выборе путей. Лучше комбинировать с BFS для уровневых графов. Ограничение: Если емкости нецелые, сходимость не гарантирована за конечное число шагов.

Когда поток максимален и что дальше

Поток максимален, когда в остаточной сети нет пути от s к t — это следует из теоремы Макс-поток Мин-разрез. Алгоритм останавливается автоматически, подтверждая оптимальность. Осталось место для улучшений: масштабируемые версии или интеграция с ML для динамических сетей.

Дальше можно изучить производные алгоритмы вроде Эдмондс-Карпа для предсказуемой сложности. Или применить на практике в задачах с несколькими источниками. Это база для глубокого погружения в графовые оптимизации.