Как выбирать путь: Эдмондс-Карп и Диниц

Если ты знаешь, почему выбор пути меняет асимптотику, помнишь оценки Эдмондса-Карпа и Диница и понимаешь, что такое слоистая сеть, листай до «Теперь сам».

Как думаешь, сколько шагов займёт эта сеть

Четыре вершины: s→a = 1000, s→b = 1000, a→b = 1, a→t = 1000, b→t = 1000. Максимальный поток очевиден - 2000, по тысяче через каждую ветку. Сколько дополняющих путей понадобится алгоритму?

Ответ зависит от того, как искать путь. Если каждый раз брать первый попавшийся и не повезёт с порядком рёбер, алгоритм будет ходить s → a → b → t, потом s → b → a → t по обратному ребру, потом снова - и каждый раз пропускать ОДНУ единицу, потому что узкое место посередине равно единице. Две тысячи шагов вместо двух. Сеть при этом крошечная.

На что это похоже

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

Механизм: три способа выбирать путь

Форд-Фалкерсон, целые ёмкости O(E · |f|)      зависит от ЧИСЕЛ на рёбрах
Эдмондс-Карп (путь кратчайший,
             обход в ширину)  O(V · E²)       от чисел не зависит
Диниц (слоистая сеть +
       блокирующий поток)     O(V² · E)       на практике заметно быстрее
     на единичных ёмкостях    O(E · √E)
     на двудольных графах     O(E · √V)       это и есть Хопкрофт-Карп

Эдмондс-Карп - это Форд-Фалкерсон, у которого поиск пути делает обход в ширину. Одна строка разницы, а оценка перестаёт зависеть от пропускных способностей.

Диниц идёт дальше. Он строит слоистую сеть: обходом в ширину размечает расстояния от s в остаточной сети и оставляет только рёбра, ведущие со слоя k на слой k + 1. В такой сети он насыщает блокирующий поток - поток, после которого ни одного пути s → t внутри слоёв не остаётся. Потом слои строятся заново, и расстояние до t обязательно увеличивается, а значит фаз не больше V.

from collections import deque


# Эдмондс-Карп: всё отличие от прошлого урока - в способе найти путь
def find_path(cap, adj, s, t):
    parent = {s: None}
    queue = deque([s])
    while queue:                      # обход в ШИРИНУ, а не в глубину
        v = queue.popleft()
        for u in adj[v]:
            if cap[v][u] > 0 and u not in parent:
                parent[u] = v
                if u == t:
                    return restore(parent, s, t)   # развернуть parent в список
                queue.append(u)                    # пар (u, v) от s до t
    return None

adj[v] содержит соседей по всем прямым и обратным рёбрам остаточной сети; текущий положительный остаток проверяется через cap[v][u]. deque.popleft() удаляет первый элемент за O(1), а перебор списков соседей суммарно смотрит O(E) рёбер. Поэтому показанный поиск имеет нужную стоимость O(E), в отличие от просмотра всех столбцов матрицы для каждой вершины. restore разворачивает цепочку parent, как в прошлом уроке.

Правило

Выбор дополняющего пути определяет асимптотику. При целых ёмкостях произвольный путь даёт O(E·|f|) - оценку, зависящую от ЧИСЕЛ, и на маленькой сети с большими пропускными способностями это тысячи шагов. Кратчайший путь (обход в ширину) даёт алгоритм Эдмондса-Карпа с оценкой O(V·E²), где чисел нет вовсе. Диниц повторяет то же слоями: строит слоистую сеть обходом в ширину и насыщает в ней блокирующий поток; фаз не больше V, итого O(V²·E), а на единичных пропускных способностях - O(E·√E). По умолчанию выбирай Диница; если пишешь руками и сеть небольшая - Эдмондса-Карпа.

Разбор: две тысячи шагов против двух

Сеть из вступления, все числа на месте: s→a = 1000, s→b = 1000, a→b = 1, a→t = 1000, b→t = 1000.

путь наугад (глубина):
   s → a → b → t   узкое место 1   (три ребра)
   s → b → a → t   узкое место 1   (обратное ребро a→b снова стало 1)
   ... и так 2000 раз, по единице за шаг

обход в ширину:
   s → a → t       узкое место 1000   (два ребра)
   s → b → t       узкое место 1000   (два ребра)
   путей нет, поток 2000

Разница не в удаче, а в длине пути. Обход в ширину физически не может выбрать трёхрёберный путь, пока существует двухрёберный, - а как только двухрёберные насыщены, длинный путь уже ничего не даёт. Именно это и доказывается в оценке Эдмондса-Карпа: расстояние от s до t в остаточной сети НИКОГДА не уменьшается, а каждое ребро может стать узким местом не чаще V/2 раз. Отсюда O(V·E) дополняющих путей, каждый ищется за O(E), итого O(V·E²).

Обрати внимание, как устроена эта оценка: в ней нет ни одной пропускной способности. Сеть с единицами и сеть с миллиардами обрабатываются одинаково долго. Для алгоритма, у которого «наивная» оценка зависела от чисел на рёбрах, это редкая и очень приятная смена жанра.

Разбор: зачем Диницу слои

Слоистая сеть - это остаточная сеть, из которой выброшено всё, что не ведёт «на шаг ближе к t». Пример: расстояния от s вышли такими - s = 0, a = 1, b = 1, c = 2, t = 3. Тогда в слоистой сети остаются только рёбра 0→1, 1→2 и 2→3; ребро a→b (слой 1 в слой 1) и любое ребро назад выбрасываются.

Что это даёт. Внутри слоистой сети алгоритм ищет пути обходом в глубину и насыщает их, пока пути не кончатся, - причём каждый шаг либо доводит путь до t (и тогда насыщает минимум одно ребро), либо упирается в тупик (и тогда вершина-тупик удаляется навсегда). Поэтому вся фаза стоит O(V·E), а не O(E) на каждый путь.

А главное - когда пути внутри слоёв кончились, кратчайшее расстояние от s до t в остаточной сети СТРОГО выросло. Расстояние - целое число от 1 до V − 1, значит фаз не больше V. Перемножаем: O(V) × O(V·E) = O(V²·E). На единичных пропускных способностях каждая фаза дешевле, а фаз не больше O(√E) - отсюда O(E·√E), и именно этот случай работает в задачах про паросочетания.

Что ломается без этого

Первое: писать Форда-Фалкерсона с обходом в глубину и удивляться, что на сети из десяти вершин программа думает минуту - числа на рёбрах попали в асимптотику. Второе: искать путь в ширину, но брать не кратчайший, а первый попавшийся из очереди при уже размеченных вершинах - тогда гарантия Эдмондса-Карпа не работает, хотя код выглядит «как обход в ширину». Третье: в Динице строить слои один раз, а не на каждой фазе: после насыщения блокирующего потока слои обязаны перестраиваться. Четвёртое: в слоистой сети не удалять тупиковые вершины - тогда обход в глубину будет заново проваливаться в один и тот же тупик, и фаза станет дороже. Пятое: ожидать, что Диниц всегда быстрее Эдмондса-Карпа на маленьких данных: асимптотика лучше, а константа больше, и на сети из десятка вершин разницы не будет.

Зачем это в работе

Готовые реализации потока живут в библиотеках, и знать их внутренности наизусть не нужно - нужно понимать, что ты выбираешь. Если задача сводится к потоку на графе с единичными пропускными способностями (а это почти все задачи про паросочетания и покрытия), бери Диница: O(E·√V) на двудольном графе - это разница между «мгновенно» и «пообедать» уже на десятках тысяч рёбер. Если сеть плотная и с большими числами, смотри в сторону алгоритмов проталкивания предпотока (push-relabel, O(V³)), которые в реальных замерах часто выигрывают у Диница. И держи в голове главное правило раздела: как только в оценке появились ЧИСЛА с рёбер, алгоритм перестал быть предсказуемым - меняй способ выбора пути.

Теперь сам

В сети s→a = 100, s→b = 100, a→b = 1, a→t = 100, b→t = 100 посчитай, сколько дополняющих путей сделает обход в ширину и сколько - неудачный порядок при обходе в глубину. И объясни, почему на ПРАВИЛЬНОСТЬ ответа выбор пути не влияет, а на число шагов влияет.