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