Конспект: отрицательные веса

Понятия

Беллман-Форд - V − 1 раз релаксировать ВСЕ рёбра. Цена O(V·E), веса любые.

Проверочный проход - ещё один проход после штатных: улучшение на нём означает отрицательный цикл.

Отрицательный цикл (достижимый из старта) - кратчайших путей НЕ СУЩЕСТВУЕТ: длину можно уменьшать бесконечно.

Путь на ДАГе - один проход в топологическом порядке, O(V + E), веса любые.

Цикл с наименьшим отношением Σc / Σt - поиск по ответу: при весах c − λ·t отрицательный цикл есть ⇔ оптимум < λ. Алгоритм Карпа - точный наименьший средний вес цикла за O(V·E) по наименьшим весам путей ровно из k рёбер.

Что унести

после k-го прохода верны все расстояния, достижимые путями из k рёбер
кратчайший путь без отрицательных циклов содержит ≤ V−1 ребра
   ⇒ V−1 прохода достаточно

Обязательная проверка dist[u] != INF перед релаксацией: иначе «бесконечность плюс отрицательный вес» даст конечную оценку недостижимой вершине.

Восстановление цикла: от вершины, улучшенной на проверочном проходе, сделать V шагов назад по prev (она может лежать вне цикла, V шагов гарантированно вводят внутрь), дальше идти до повтора.

Важна ДОСТИЖИМОСТЬ цикла: цикл в стороне расстояниям не мешает. Чтобы найти отрицательный цикл где угодно в графе, добавляют фиктивную вершину с рёбрами нулевого веса во все остальные.

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

Практика: арбитраж валют (вес = минус логарифм курса, прибыль = отрицательный цикл), системы разностных ограничений (x_j − x_i <= c; отрицательный цикл = система несовместна), критический путь в планировании (длиннейший путь на ДАГе), дистанционно-векторная маршрутизация.

Куда это ведёт

Следующая глава - расстояния между ВСЕМИ парами: Флойд-Уоршелл и Джонсон, где потенциалы как раз и понадобятся.