Алгоритм Диница

Сколько аэропортов должно закрыться одновременно — из-за погоды, забастовки, пепла после извержения, — чтобы из Алматы нельзя было долететь до Лимы? Столько же, сколько найдётся маршрутов, у которых нет ни одной общей пересадки: каждый такой маршрут надо перекрыть отдельно, и этого хватает. Ниже сеть рейсов всего мира, 3468 аэропортов и 84 869 направлений, и алгоритм Диница, который ищет эти маршруты не по одному, а фазами. Нажмите на любой аэропорт, чтобы сменить цель.

Из Алматы в Лиму ведут 52 маршрута, и ни через один аэропорт не проходят два из них. Диницу понадобилось девять фаз. В первой нашёлся один маршрут из двух перелётов — через Амстердам, во второй сразу 22 из трёх, в третьей 14 из четырёх, дальше всё меньше и всё длиннее. Переключите на Эдмондса — Карпа: маршруты те же 52, но обходов в ширину 53 вместо 10, и проверок дуг 7,2 миллиона вместо 2,9.

Кольцами в конце отмечен разрез — 52 аэропорта. Сорок из них летают в Лиму сами. Остальные двенадцать, среди них Франкфурт, Варшава, Тенерифе, Дакар, Лиссабон, Ресифи, — пересадки, через которые проходят маршруты к другим аэропортам, откуда в Лиму есть рейс. Закройте все 52, и в Лиму из Алматы не попасть. Меньшим числом не обойтись: через каждый закрытый аэропорт проходит ровно один из 52 маршрутов.

Подписи к шагам рассказывают и о другом. Десять путей из 52 проходят какой-нибудь рейс задом наперёд. Это не полёт назад, а отмена: рейс снимается с найденного раньше маршрута, тот продолжается по-другому, и маршрутов становится на один больше. Так устроен любой алгоритм потока — об этом статья о наибольшем потоке.

Идея

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

Пусть d(v) — расстояние в дугах от истока до v по остаточной сети. Оставим только дуги, которые ведут ровно на слой глубже, из u в v с d(v) = d(u) + 1. Получится слоистая сеть. Любой путь из истока в сток по ней кратчайший, и наоборот: каждый кратчайший путь остаточной сети лежит в ней целиком.

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

Обойдите остаточную сеть в ширину и оставьте дуги, ведущие на слой глубже. Пускайте по ним пути поиском в глубину, пока каждый путь из истока в сток не упрётся в заполненную дугу, — это фаза. Повторяйте фазы, пока сток достижим.

Блокирующий поток ищут поиском в глубину, но с одной деталью, без которой всё бессмысленно. У каждой вершины u есть указатель nxt[u] — номер первой исходящей дуги, которую ещё стоит пробовать. Если дуга заполнена или ведёт в тупик, указатель сдвигается и в этой фазе к ней больше не вернётся. Вершина, из которой не осталось дуг, — тупик: поиск отступает, и указатель вершины перед ней тоже сдвигается. Найдя путь до стока, поиск пускает по нему поток и начинает снова от истока, но всё отброшенное помнят указатели.

Вот фазы для маршрутов из Алматы в Куинстаун. Чтобы схема читалась, на ней только аэропорты, из которых внутри слоёв ещё есть путь до цели. Остальные поиск тоже посещает и тут же отступает — их видно только в счётчике тупиков.

В первой фазе до Куинстауна не меньше трёх перелётов, и на путях такой длины лежат 27 аэропортов, куда из Алматы есть прямой рейс, и 6, откуда есть прямой рейс в Куинстаун: Окленд, Крайстчерч, Брисбен, Голд-Кост, Мельбурн и Сидней. Поиск пускает шесть маршрутов, по одному через каждый из шести. После этого рейсы из Алматы ещё свободны — в 21 аэропорт первого столбца, — но дальше не пройти: все шесть последних пересадок заняты. Фаза кончается, хотя пройдены далеко не все дуги. Вторая фаза строит слои заново, и самый короткий свободный путь теперь в четыре перелёта: через Гонконг, Нади и Веллингтон. Третья фаза до Куинстауна не доходит. Ответ — семь маршрутов, и разрез из семи аэропортов — ровно те семь, откуда в Куинстаун есть рейс.

Счётчик под схемой показывает цену. В первой фазе поиск в настоящей сети отступал 19 992 раза — из аэропортов, откуда за оставшиеся перелёты в Куинстаун не попасть. Таких почти вся сеть: за три перелёта из Алматы можно добраться почти куда угодно, но в Куинстаун — только через шесть аэропортов. Зато каждый тупик поиск проверял целиком лишь однажды, а потом отскакивал от него за один шаг: указатель уже стоял в конце его списка дуг.

Почему фаз мало

Всё держится на одном свойстве: фаза делает сток дальше.

Расстояние — от 1 до V − 1 и с каждой фазой растёт хотя бы на единицу, поэтому фаз не больше V − 1. Осталось понять, сколько стоит одна.

Вместе с обходом в ширину за O(E) на фазу получается O(V² E) на весь алгоритм. У Эдмондса — Карпа оценка O(V E²): в плотной сети, где E близко к V², разница в V раз.

Единичные сети

Сеть аэропортов устроена особо. Каждый аэропорт, кроме начала и конца, разрезан на две вершины, прилёт и вылет, с дугой ёмкости 1 между ними, у всех рейсов тоже ёмкость 1. Получается единичная сеть: все ёмкости равны 1, и у каждой вершины, кроме истока и стока, ровно одна входящая дуга (у вылета) или ровно одна исходящая (у прилёта). Через такую вершину не пройдёт больше единицы. Тут Диниц гораздо быстрее общей оценки.

Во-первых, фаза стоит O(E), а не O(V E): когда ёмкости единичные, путь до стока заполняет все свои дуги, и каждая дуга за фазу побывает на удачном пути не больше одного раза. Шагов вперёд тогда не больше 2E. Во-вторых, фаз мало.

Для сети рейсов V = 6936, и оценка обещает не больше 167 фаз. На деле до Лимы их девять, до Кейптауна три. Та же теорема даёт и оценку алгоритма Хопкрофта — Карпа: пары в двудольном графе — это поток в единичной сети из истока, двух долей и стока, и Хопкрофт — Карп ровно Диниц на ней, подробности — в статье о паросочетаниях. Если же единичны только ёмкости, а через вершину может идти много путей, Шимон Ивен и Роберт Тарьян в 1975 году показали, что фаз O(min(√E, V^2/3)).

Код

Сеть хранится, как в статье о наибольшем потоке: дуги парами, пара дуги a — это a ^ 1, остаточная сеть — массив cap. Аэропорт v превращается в прилёт 2v и вылет 2v + 1. Обход в ширину останавливается, когда дошёл до слоя стока: вершины глубже в слоистую сеть всё равно не попадут. Поиск в глубину написан без рекурсии, со стеком дуг пути: в общей сети путь может быть длиной в тысячи вершин, а глубина рекурсии в Python ограничена тысячей.

Число перелётов в пути по слоям — (уровень стока + 1) / 2: путь проходит по дуге рейса, потом по дуге внутри аэропорта, и так до цели. Через каждый аэропорт идёт не больше одного маршрута, поэтому поток раскладывается на маршруты однозначно: из каждого аэропорта выходит не больше одного рейса с потоком. Самый короткий маршрут до Лимы — через Амстердам, самый длинный — восемь перелётов, через Эль-Аламейн, Катовице, Пуэрто-Плату, Виллемстад, Белу-Оризонти, Барилоче и Мендосу. Так далеко приходится обходить, когда все короткие пути заняты другими маршрутами.

Сколько это стоит

Замер на той же сети рейсов. Берём k аэропортов с наибольшим числом направлений и рейсы между ними и считаем, сколько маршрутов без общих аэропортов могут одновременно вести с запада (западнее 30° з. д.) на восток (восточнее 30° в. д.). На всей сети таких маршрутов 165. Ещё одна линия — Диниц с ошибкой: указатели сбрасываются после каждого найденного пути.

На всей сети Диниц быстрее Эдмондса — Карпа в 9,5 раза на Python и в 7,7 раза на Go. Без указателей от этого выигрыша почти ничего не остаётся: каждый путь заново пробует все тупики, и фаза стоит столько же обходов, сколько в ней путей.

Выигрыш берётся оттого, что в одной фазе много путей одной длины. Если путей мало и все разной длины, фаз почти столько же, сколько путей, и Диниц делает ту же работу, что Эдмондс — Карп, да ещё обходит слои целиком, а не до первого попадания в сток. Для огромных сетей вроде изображений чаще берут другие алгоритмы — проталкивание предпотока Голдберга и Тарьяна или поток Бойкова — Колмогорова из статьи о разрезах.

Где легко ошибиться

• Забыть указатели. Самая частая ошибка: поиск в глубину с отметками «посещено», которые сбрасываются перед каждым путём. Алгоритм остаётся верным, но, как видно на замере, теряет почти всю скорость.
• Сдвинуть указатель после удачного пути. Если ёмкости больше единицы, дуга после пути может остаться незаполненной, и по ней пройдёт ещё один путь. Указатель сдвигается, только когда дуга заполнена или ведёт в тупик. В рекурсивных реализациях это выглядит так: после удачного рекурсивного вызова функция возвращается, не сдвигая указатель.
• Рекурсия. Рекурсивный поиск короче, но в Python глубина по умолчанию — тысяча вызовов, а путь по слоям бывает длиннее. Отсюда стек в нашем коде.
• Слои по исходной сети. Слои считают по остаточной сети — с обратными дугами и без заполненных. Если строить их по исходной сети, отмен не будет и ответ может оказаться меньше наибольшего, а условие остановки «сток недостижим» не сработает никогда.
• Указатели из прошлой фазы. Указатели обнуляют в начале каждой фазы: слои после неё другие, и дуга, отброшенная в прошлой фазе, теперь может вести на слой глубже. Если завести массив один раз на весь алгоритм, фаза может не найти ни одного пути, хотя сток достижим, и алгоритм зациклится.

Где работает

Алгоритм Диница — стандартный поток в олимпиадных библиотеках. В AtCoder Library функция наибольшего потока — это он: массивы level и iter, обход в ширину и поиск в глубину, а в документации прямо написано O((n + m)√m) для единичных ёмкостей и O(n²m) в общем случае. В networkx есть функция dinitz. Пары в двудольном графе и пути без общих вершин — его частные случаи, и оценки для них дала теорема о единичных сетях. Ивен и Тарьян построили на ней проверку вершинной связности графа: сколько вершин надо удалить, чтобы граф распался, — это наименьший разрез в единичной сети, как в нашей сцене с аэропортами.

История

Ефим Диниц придумал алгоритм в январе 1969 года, когда был студентом в группе Георгия Адельсон-Вельского — того самого «АВ» из АВЛ-деревьев. Это был ответ на упражнение из курса алгоритмов. Статья вышла в 1970 году и уместилась в четыре страницы — таков был лимит журнала, — поэтому оказалась очень сжатой. В исходной версии слоистая сеть была структурой данных, которую алгоритм поддерживал по ходу работы, а время оценивалось тонким амортизационным анализом.

Шимон Ивен и его аспирант Алон Итаи заинтересовались статьёй Диница и статьёй Александра Карзанова, где появилось понятие блокирующего потока. За три дня они разобрали обе, кроме того, как поддерживать слоистую сеть. Этот пробел закрыли сами: взяли блокирующий поток Карзанова и стали искать каждый путь поиском в глубину. Ивен потом годами рассказывал этот вариант на лекциях, и в таком виде — обход в ширину для слоёв, поиск в глубину для путей — алгоритм теперь и учат. Фамилию в английском переводе статьи записали как Dinic, на лекциях её произносили «Диник», и по-английски алгоритм так и называется: Dinic's algorithm. В 2003 году Диниц сам сказал, что соединение поиска в ширину с поиском в глубину — заслуга Ивена и Итаи, а Ивен, рассказывая об алгоритме, добавлял, что Диниц придумал его в девятнадцать лет и первым опубликовал амортизационную оценку времени.

Независимо от Диница Джек Эдмондс и Ричард Карп в 1972 году показали, что кратчайшие увеличивающие пути не становятся короче, — это их теорема. Карзанов в 1974 году нашёл блокирующий поток за O(V²) проталкиванием предпотоков, и общая оценка стала O(V³). Дальше были динамические деревья Слитора и Тарьяна и проталкивание Голдберга и Тарьяна, а в 2022 году — алгоритм почти линейного времени, о котором рассказывает глава курса.

Задачи

В первой задаче нужны маршруты только наименьшей длины, и одной фазы для них не хватит: блокирующий поток не обязан быть наибольшим. Во второй тысячи названий делят трёхбуквенные коды, и решению нужна оценка единичных сетей — по одному пути за обход не успеть.