Два алгоритма: дешёвые пути и отмена циклов

Коротко

Алгоритмов два, и оба выводятся из критерия прошлого урока. Последовательные кратчайшие пути (SSP): дополнять поток не по любому пути, а по самому дешёвому - тогда после каждого шага поток остаётся самым дешёвым среди потоков своей величины. Отмена циклов: взять любой поток нужной величины и, пока в остаточной сети есть отрицательный цикл, прогонять по нему положительную величину не больше минимального остатка на цикле. Дешёвый путь ищут Беллманом-Фордом - обратные рёбра могут иметь отрицательные цены, и обычная Дейкстра не гарантирует ответ; лечится это потенциалами Джонсона из раздела про кратчайшие пути, и тогда каждый шаг снова считается Дейкстрой за O(E·log V).

Для обоих приведённых псевдокодов нижние границы потоков равны 0. В примерах исходные цены неотрицательны, ёмкости и нужная величина потока целые. При нулевых нижних границах более общее условие старта с пустого потока - отсутствие отрицательных циклов в исходной сети. Одна лишь пустота потока этого не гарантирует.

Если ты знаешь оба алгоритма, понимаешь, почему нужен Беллман-Форд, и помнишь, как потенциалы возвращают Дейкстру, листай до «Теперь сам».

Как думаешь, почему нельзя просто взять Дейкстру

Поиск самого дешёвого дополняющего пути - это задача о кратчайшем пути, а её мы умеем решать быстро. Казалось бы, ставь Дейкстру и радуйся. Что не так?

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

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

Пересчёт маршрута с учётом возвратов. Пока ты только покупаешь билеты, цены положительные и навигатор по ценам работает. Как только появляется возможность СДАТЬ билет и получить деньги обратно, часть «рёбер» становится отрицательной - и наивный поиск дешёвого маршрута начинает ошибаться, потому что он привык, что дорога вперёд не бывает выгоднее, чем стоять на месте.

Механизм: SSP и отмена циклов

ПОСЛЕДОВАТЕЛЬНЫЕ КРАТЧАЙШИЕ ПУТИ (SSP)
    поток пустой
    пока величина меньше нужной:
        найти САМЫЙ ДЕШЁВЫЙ путь s → t в остаточной сети   (Беллман-Форд)
        пустить min(узкое место пути, K − текущая величина)
    инвариант: после каждого шага поток - самый дешёвый среди потоков своей величины

ОТМЕНА ЦИКЛОВ (cycle canceling)
    найти любой поток ровно K: дополнять, ограничивая шаг остатком K−|f|
    пока в остаточной сети есть отрицательный цикл:
        прогнать по нему величину узкого места
    останавливается ровно по критерию прошлого урока

Цена вопроса:

SSP с Беллманом-Фордом:   O(K · V · E),  K - величина потока
SSP с потенциалами:       O(K · E · log V)   (каждый шаг - Дейкстра)
                         + O(V · E) на начальные потенциалы,
                           если исходные цены отрицательны
отмена циклов:            зависит от выбора цикла; наивная версия слабо ограничена,
                         минимальная средняя цена цикла даёт полиномиальную версию

Алгоритм поиска начального потока останавливай ровно при K; если максимально достижимая величина меньше K, задача неразрешима. Множитель K в оценках SSP предполагает целые ёмкости и целочисленный старт: каждый шаг увеличивает поток хотя бы на 1. Для дробных ёмкостей одного значения K недостаточно.

Средняя цена цикла - сумма цен его рёбер, делённая на число рёбер. Здесь выбирают минимум этой величины, а не максимум общего снижения стоимости за один шаг: это разные критерии. Для исходных отрицательных циклов добавляется и работа их отмены; оценка SSP в таблице относится к старту без таких циклов.

Потенциалы Джонсона здесь работают точно так же, как в разделе про кратчайшие пути. При неотрицательных исходных ценах можно начать с p[v]=0: все используемые остаточные рёбра тогда имеют неотрицательную цену. Если исходные отрицательные рёбра есть, но отрицательных циклов нет, сначала получают допустимые потенциалы Беллманом-Фордом: добавляют временный источник с нулевыми рёбрами во все вершины и берут расстояния от него. Неравенство кратчайших путей даёт a(u,v)+p[u]−p[v]≥0. Например, для единственного ребра s→t цены −5 нулевые потенциалы не подходят, а p[s]=0,p[t]=−5 дают цену 0.

После шага Дейкстры к потенциалам достигнутых вершин прибавляют найденные расстояния. Для достигнутого ребра dist[v]≤dist[u]+a'(u,v), поэтому новая приведённая цена неотрицательна. На кратчайшем пути она равна нулю, значит новые обратные рёбра тоже имеют нулевую приведённую цену. При фиксированном истоке достаточно сохранять это условие в достижимой части сети; до недостижимых вершин расстояния бесконечны, и прибавлять бесконечность к потенциалам нельзя. Кратчайшие пути после перевзвешивания остаются теми же, потому что к цене каждого пути добавляется одна разность потенциалов концов.

Если отрицательный цикл есть уже на пустом потоке, сначала устраняют его циркуляцию алгоритмом отмены циклов. Иначе нулевой поток может быть не самым дешёвым потоком величины 0, а поиск кратчайших путей не даёт нужного старта. Отрицательные рёбра и отрицательные циклы - разные препятствия: первые лечатся потенциалами, вторые нарушают инвариант оптимальности.

Правило

SSP: начать с минимального по стоимости потока своей величины и дополнять его по самому дешёвому пути в остаточной сети; инвариант - после каждого шага поток минимален по стоимости среди потоков своей величины, поэтому в конце получается ответ. Отмена циклов: начать с любого потока нужной величины и убирать отрицательные циклы, пока они есть. Искать дешёвый путь надо Беллманом-Фордом, поскольку обратные рёбра могут иметь отрицательные цены; потенциалы Джонсона делают цены неотрицательными и возвращают Дейкстру, не меняя кратчайших путей. Цена SSP - O(K·V·E) наивно и O(K·E·log V) с уже допустимыми потенциалами, где K - целая величина потока. Если исходные отрицательные цены требуют Беллмана-Форда для инициализации, добавляется O(V·E).

Разбор: SSP на сети курьеров

Возьмём двух курьеров и две задачи. Цены: курьер A - 1 и 5; курьер Б - 2 и 3. Сеть: исток → курьеры (1, цена 0), курьеры → задачи (1, цена как в таблице), задачи → сток (1, цена 0).

шаг 1. самый дешёвый путь: s → A → задача 1 → t,  цена 1
       поток 1, стоимость 1

шаг 2. остаточная сеть: ребро s→A насыщено, второй раз в A из истока не войти;
       у задачи 1 появилось обратное ребро в A с ценой −1
       пути:  s → Б → задача 2 → t                        цена 3
              s → Б → задача 1 → A → задача 2 → t         цена 2 + (−1) + 5 = 6
       берём первый: поток 2, стоимость 1 + 3 = 4

Ответ: 4, то есть A берёт первую задачу, Б - вторую. Проверим перебором: вторая расстановка A-2, Б-1 стоит 5 + 2 = 7. Всё верно.

Обрати внимание на второй шаг: алгоритм РАССМОТРЕЛ путь с обратным ребром, где часть уже сделанного назначения отменяется, и отверг его по цене. В этом и разница с жадностью - она такие варианты даже не видит. На пятёрке курьеров выбор пути по цене даёт 13. Без учёта цены можно получить диагональное назначение за 13+11+2+9+8=43; это один возможный исход, а не обязательный результат любого порядка обхода.

Разбор: почему SSP не ломается на отрицательных рёбрах

Может показаться, что алгоритм сам себе создаёт проблему: он ведь вносит в сеть отрицательные рёбра. Спасает инвариант.

если поток минимален по стоимости среди потоков своей величины,
то в остаточной сети НЕТ отрицательных циклов            (критерий прошлого урока)

значит кратчайший путь в ней определён корректно:
Беллман-Форд на графе без отрицательных циклов работает

а дополнив поток по кратчайшему пути,
мы получаем поток, минимальный среди потоков НОВОЙ величины

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

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

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

Первое: искать дешёвый путь обычной Дейкстрой при отрицательных остаточных ценах без допустимых потенциалов - правильный ответ больше не гарантирован. Второе: запускать SSP с произвольного потока - инвариант нарушен, ответ занижен по величине или завышен по цене. Третье: в отмене циклов брать первый попавшийся отрицательный цикл и надеяться на быстрое завершение: наивный выбор плохо ограничен по числу шагов; полиномиальная версия выбирает цикл минимальной средней цены. Четвёртое: забыть, что потенциалы надо ОБНОВЛЯТЬ после каждого шага, а не считать один раз. Пятое: считать, что стоимость надо пересчитывать по всей сети - она накапливается по шагам как delta · (цена пути).

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

Готовые реализации потока минимальной стоимости есть в библиотеках (networkx, OR-Tools, LEMON), и обычно берут именно их. Знание внутренностей нужно ровно для двух вещей. Первая - понять цену: K в оценке O(K·E·log V) - это ВЕЛИЧИНА потока, поэтому сеть с пропускными способностями в миллион и сеть с единицами считаются по-разному, и большие ёмкости лечатся масштабированием. Вторая - правильно поставить задачу: чаще всего в реальности нужен не максимальный поток минимальной стоимости, а поток заданной величины (развезти ровно столько-то товара), и это разные постановки с разным ответом.

Теперь сам

Сеть: s→a = 2 (цена 0), s→b = 2 (цена 0), a→t = 1 (цена 1), b→t = 1 (цена 4), a→b = 1 (цена 1). Нужно пропустить 2 единицы. Прогони SSP, назови стоимость и проверь ответ критерием.

Ответ. Все пути из s в t и их цены за единицу:

s → a → t          0 + 1     = 1      пропускает 1 (мешает a→t)
s → b → t          0 + 4     = 4      пропускает 1 (мешает b→t)
s → a → b → t      0 + 1 + 4 = 5      пропускает 1 (мешает a→b и b→t)

Шаг 1: самый дешёвый - s→a→t за 1, узкое место 1. Поток 1, стоимость 1.

Шаг 2: a→t насыщено. Из оставшихся дешевле s→b→t за 4. Поток 2, стоимость 1 + 4 = 5.

Проверка критерием. В остаточной сети: a→t и b→t насыщены, вместо них появились обратные t→a с ценой −1 и t→b с ценой −4; a→b свободно (цена 1); у s→a и s→b остался запас по единице. Двухрёберные циклы s→a→s и s→b→s стоят 0. Единственный другой простой цикл - a→b→s→a стоимости 1+0+0=1. У t нет входящих остаточных рёбер, поэтому он в цикл не входит. Любой замкнутый маршрут разлагается на эти простые циклы; отрицательных нет, значит 5 и есть минимум.

Перебирать маршруты глазами годится на четырёх вершинах; машинно это делает Беллман-Форд за O(V·E): стартовать с dist = 0 во ВСЕХ вершинах сразу и после V проходов сделать ещё один - если он что-то улучшил, отрицательный цикл есть.

Полезное наблюдение напоследок: обход в ширину на этой сети выбрал бы те же два двухрёберных пути и дал бы ту же пятёрку. Маленькие сети часто не различают алгоритмы - и именно поэтому задача главы включает пятёрку курьеров с оптимумом 13 и допустимым диагональным назначением за 43.

Главное

Два алгоритма растут из одного критерия. Последовательные кратчайшие пути: дополнять по самому дешёвому пути из минимального по стоимости старта; пустой поток подходит при отсутствии исходных отрицательных циклов. Инвариант - поток остаётся минимальным по стоимости среди потоков своей величины. Отмена циклов: взять любой поток нужной величины и убирать отрицательные циклы, пока они есть. Дешёвый путь ищется Беллманом-Фордом: обратные рёбра могут иметь отрицательную цену; потенциалы Джонсона делают цены неотрицательными, возвращают Дейкстру и дают O(K·E·log V) вместо O(K·V·E) после получения допустимых потенциалов. Начальный Беллман-Форд при отрицательных исходных ценах добавляет O(V·E). Величина потока K стоит прямо в оценке - большие пропускные способности лечатся масштабированием.