В 1956 году американские математики Лестер Форд, соавтор алгоритма Беллмана–Форда, и Делберт Фалкерсон предложили метод поиска максимального потока в транспортной сети. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов разбирают подход на сети из 5 вершин, где тот за три прохода набирает поток в 37 единиц.
Рис. 1. Транспортная развязка – та же задача о максимальном потоке, только в бетоне
Перед созданием алгоритма учёные доработали теорему Менгера, превратив её в частный случай. Австриец допускал единичную пропускную способность рёбер, американцы развили идею до любых неотрицательных весов. Обобщённая версия получила имя авторов, поэтому в литературе встречается и теорема Форда–Фалкерсона. Работа вышла отчётом корпорации RAND и почти сразу пригодилась военной логистике: по ней считали пропускную способность железнодорожной сети в Восточной Европе того времени.
Подход Форда–Фалкерсона – вариация жадного алгоритма с нюансом: поток максимизируется с опорой не на исходный граф, а на его модифицированную версию – остаточную сеть. В ней у каждого ребра появляется двойник, ведущий назад.
Из преимуществ – простота идеи, полное использование загрузки путей, лёгкость программной реализации и работа с целыми и вещественными значениями. Метод хорошо масштабируется на крупные сети и не требует предварительной подготовки данных.
К недостаткам относят зависимость от величины максимального потока и большое число итераций на крупных сетях с высокой пропускной способностью – такие случаи требуют дополнительных улучшений. Подход слаб в параллельном применении и на плотных графах.
Для работы определяют начальную вершину (исток) и конечную (сток). От точки старта строят путь до финиша, выбирая самые ёмкие рёбра, и пускают поток. Загрузка подчиняется правилу «бутылочного горлышка»: наименьший вес ребра в цепочке и задаёт возможный поток. Операции повторяют, пока допустимые пути не окажутся забитыми.
Разберём метод на примере. Дан граф из 5 вершин: некоторые точки связаны рёбрами, движение задано, веса установлены (рисунок 2). Нужно организовать поток из вершины 0 в 4. Значения рёбер продублированы в таблице под заголовком «пропускная способность». Обратите внимание: прямого ребра из истока в сток нет, поэтому любой поток пойдёт транзитом через промежуточные точки сети и упрётся в их ограничения.
Рис. 2. Начальный граф: исток – вершина 0, сток – вершина 4
Для вехи 0 отбираем ребро с максимальным значением. Условию удовлетворяет 0–3 ценой 18. У точки 3 единственный смежный вектор ведёт в 4, поэтому используем его (рисунок 3).
Рис. 3. Путь до стока 0–3–4
Считаем пропускную способность. Минимум в цепочке равен 18, поэтому ребро 0–3 превращается в 0/18: свободного места на направлении не осталось. У пары 3–4 то же действие даёт 19/18, где слева остаток, а справа занятое (рисунок 4). Из-за модификаций исходный граф получает рёбра обратного направления, и позже они дадут алгоритму второй шанс переложить часть потока по другому маршруту сети.
Рис. 4. Остаток и загрузка после первого потока в 18 единиц
Для вершины 0 остаются два равновесных ребра, и алгоритм выбирает случайно. Пусть выпало 0–2. Тогда движение получает комбинацию 0–2–3–4 с пропуском в 6 единиц.
Рис. 5. Второй путь 0–2–3–4 добавляет 6 единиц
Новый путь обретает очертания 0–1–3–4: ребро 1–3 больше, чем 1–4. Обнуляются два ребра, 0–1 и 3–4. Проверка оставшегося моста 0–2 показывает, что дальше пути нет, поэтому можно считать итог: 18 + 6 + 13 = 37 единиц. Ни одна цепочка из истока в сток больше не имеет свободного места сразу на всех рёбрах маршрута.
Рис. 6. Третий путь 0–1–3–4 закрывает граф: максимум 37 единиц
Для демонстрации обратных рёбер проведём эксперимент. Предположим, есть дополнительное соединение 1–2, использованное на одном из предыдущих шагов. Первоначальный вес был 10, после применения соотношение стало 3/7 (рисунок 7).
Рис. 7. Граф с дополнительным ребром 1–2, уже загруженным на 7 единиц
Теперь удаётся проложить дополнительный путь до точки 4: 0–2–1–4. Это возможно благодаря обратным рёбрам. Поскольку идём против исходного направления, пропускная способность корректируется: у пары 2–1 значение меняется на 10/0. Алгоритм отменяет часть прежнего решения и переливает поток выгоднее.
Рис. 8. Обратное ребро открывает путь 0–2–1–4 и поднимает максимум до 44
Дополнительно провели 7 единиц, поэтому итог растёт на столько же: максимальная пропускная способность графа с добавленным ребром составляет 44 единицы.
Операции с обратными рёбрами в остаточной сети позволяют алгоритму искать спрятанные максимумы, а не останавливаться на локальных оптимумах. Перенаправление потоков – классический приём транспортников.
Подход Форда–Фалкерсона легко воспринимается головой и повторяется на малых графах вручную. При росте числа вершин и рёбер придётся обратиться к инструментам программирования и автоматизации расчёта.
Временная сложность метода зависит от величины максимального потока:
T = O(E · max|f|),
где T – время работы, E – количество рёбер, max|f| – величина максимального потока.
Требования к памяти зависят от числа вершин и рёбер:
Q = O(V + E) – для общего случая,
Q = O(V2) – для матрицы смежности,
где Q – объём памяти, V – число вершин, E – количество рёбер.
Когда применять алгоритм?
Подход создан для сетевых задач: транспортных, водопроводных, информационных. Им распределяют задачи между сотрудниками и ресурсы между производствами, ищут совпадения в рекомендациях, считают потоки пассажиров и балансируют нагрузку.
В чём преимущество Форда–Фалкерсона?
Алгоритм выдаёт оптимальные дороги для максимальной доставки и подходит для широкого круга задач. У метода понятная последовательность шагов, что даёт предсказуемость при поиске решений. Программный код легко составляется и адаптируется под нужды.
Сколько проходов делает алгоритм?
Количество шагов напрямую зависит от пика загрузки. Подход ищет возможности для движения как по имеющимся направлениям, так и по обратным. Последние возникают в остаточной сети – модифицированной версии исходного графа.
Где Форд–Фалкерсон проигрывает?
Метод не подойдёт для задач с минимальной стоимостью потока. Слабо проявляет себя, если исходных или конечных точек несколько. На изменчивых сетях алгоритм будет сбоить: пересчёт потребуется после каждого преобразования.
Чем Форд–Фалкерсон отличается от Эдмондса–Карпа?
Правилом выбора пути. Форд–Фалкерсон его не оговаривает: годится любая цепочка с остатком, и выше мы брали самые ёмкие рёбра. Эдмондс и Карп в 1972 году потребовали брать кратчайший путь – поиском в ширину, – и число итераций перестало зависеть от весов на рёбрах. Оценка стала O(V · E2), а зацикливание на дробных пропускных способностях исчезло.
Что запомнить?
Алгоритм Форда–Фалкерсона предпочитает двигаться по крупным рёбрам, но проводит по ним допустимый для пути минимум. Метод способен направлять движение в обе стороны. Он применим для широкого спектра задач: от логистической доставки и построения коммуникационных сетей до расписаний, распределения ресурсов и рекомендаций.
Максимальный поток равен минимальному разрезу – в этом и состоит теорема Форда–Фалкерсона. Найдя поток, вы одновременно получаете самое узкое место сети: набор рёбер, расширение которых поднимет пропуск, тогда как любые другие вложения пропадут зря.
Рис. 9. Пять шагов Форда–Фалкерсона и цифры разобранной сети