Алгоритм Джонсона: как сделать веса неотрицательными честно

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

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

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

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

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

Механизм: потенциалы и перевзвешивание

Это описание словами, а не листинг: каждый шаг - вызов алгоритма, который уже разобран.

1) добавить фиктивную вершину q и рёбра q → v весом 0 для каждой вершины v
2) Беллман-Форд из q  →  h[v] = кратчайшее расстояние от q до v
   (если он нашёл отрицательный цикл - на этом всё, задача решения не имеет)
3) перевесить каждое ребро:  w'(u, v) = w(u, v) + h[u] − h[v]
4) V раз запустить Дейкстру по новым весам  →  d'(u, v)
5) вернуть настоящие расстояния:  d(u, v) = d'(u, v) − h[u] + h[v]

Почему новые веса неотрицательны. Величина h - это кратчайшие расстояния от q, а для них выполняется неравенство треугольника: h[v] <= h[u] + w(u, v) (иначе путь до v через u был бы короче, чем «кратчайший»). Переносим: w(u, v) + h[u] − h[v] >= 0. То есть w' >= 0 для каждого ребра - ровно то, что требуется Дейкстре.

Почему кратчайшие пути не меняются. Возьмём любой путь u = v₀ → v₁ → ... → v_k = v и сложим новые веса. Ниже v_i - это i-я вершина ПУТИ (не вершина с номером i в графе), а v_i+1 - следующая за ней, то есть v с индексом i + 1:

Σ w'(v_i, v_i+1) = Σ [ w(v_i, v_i+1) + h[v_i] − h[v_i+1] ]
                 = Σ w(v_i, v_i+1) + (h[v₀] − h[v₁]) + (h[v₁] − h[v₂]) + ... + (h[v_k−1] − h[v_k])
                 = (длина пути) + h[u] − h[v]

Промежуточные потенциалы сокращаются («телескопическая сумма»), и остаётся добавка h[u] − h[v], одна и та же для ВСЕХ путей между этой парой. Значит порядок путей по длине сохраняется: кратчайший остаётся кратчайшим.

Цена: O(V·E) на Беллмана-Форда плюс V Дейкстр - O(V·E·log V) на двоичной куче. Сравни с O(V³) Флойда: на разреженном графе (E ≈ V) это O(V²·log V) против O(V³) - выигрыш в V / log V раз (логарифм, как всюду в курсе, двоичный). В числах при V = 1000: log₂ 1000 ≈ 10, значит Джонсон делает порядка 10⁷ операций против 10⁹ у Флойда - в сотню раз меньше. А вот при V = 100 разрыв уже 15-кратный, и Флойд с его пятью строками часто оказывается разумнее.

Правило

Джонсон: добавить фиктивную вершину с нулевыми рёбрами ко всем, Беллманом-Фордом посчитать потенциалы h[v], перевесить рёбра как w'(u, v) = w(u, v) + h[u] − h[v] (получается неотрицательно по неравенству треугольника), V раз запустить Дейкстру и вернуть расстояния как d = d' − h[u] + h[v]. Кратчайшие пути сохраняются, потому что длина ЛЮБОГО пути из u в v меняется на одну и ту же величину h[u] − h[v] (телескопическая сумма). Цена O(V·E·log V) - выгоднее O(V³) на разреженных графах.

Разбор: считаем потенциалы на маленьком графе

Граф: a→b = 3, b→c = −2, a→c = 4, c→a = 5.

Добавляем q с рёбрами нулевого веса в a, b, c и считаем Беллманом-Фордом: h[a] = 0 (прямое ребро из q), h[b] = 0 (тоже прямое; путь через a дал бы 3 - хуже), h[c] = −2 (путь q → b → c стоит 0 + (−2), это лучше нуля).

Перевешиваем:

w'(a, b) = 3 + h[a] − h[b] = 3 + 0 − 0      = 3
w'(b, c) = −2 + h[b] − h[c] = −2 + 0 + 2    = 0
w'(a, c) = 4 + h[a] − h[c] = 4 + 0 + 2      = 6
w'(c, a) = 5 + h[c] − h[a] = 5 − 2 − 0      = 3

Все новые веса неотрицательны - можно звать Дейкстру. Проверим, что ответ не испортился. По новым весам кратчайший путь из a в c: напрямую 6 или через b: 3 + 0 = 3 - побеждает через b. Пересчитываем обратно: d(a, c) = d'(a, c) − h[a] + h[c] = 3 − 0 + (−2) = 1. По исходным весам путь a → b → c стоит 3 + (−2) = 1 - сходится, и это действительно лучше прямого ребра весом 4.

Разбор: зачем фиктивная вершина

Можно было бы взять h[v] равным расстоянию от какой-нибудь настоящей вершины - но тогда вершины, недостижимые из неё, получили бы h = +∞, и формула перевзвешивания развалилась бы. Фиктивная вершина q соединена нулевыми рёбрами СО ВСЕМИ, поэтому достижимо всё, и все потенциалы конечны.

Заодно она ничего не портит: из q рёбра только выходят, значит в кратчайшие пути между настоящими вершинами она попасть не может. А ещё она даёт полезный побочный эффект - Беллман-Форд из q видит ВСЕ отрицательные циклы графа, а не только достижимые из какой-то одной вершины. Если цикл есть, алгоритм честно останавливается: расстояний не существует, считать нечего.

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

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

Первое: перевешивать как w + h[v] − h[u] (перепутать знаки) - веса станут отрицательными, и Дейкстра снова окажется неприменима. Второе: забыть пересчитать расстояния обратно и выдать d' как ответ - числа будут неверными везде, кроме пар с равными потенциалами. Третье: брать потенциалы от настоящей вершины вместо фиктивной - у недостижимых получится бесконечность. Четвёртое: применять Джонсона к графу с отрицательным циклом: Беллман-Форд обязан отработать первым и остановить всё. Пятое: тащить Джонсона на плотный граф - там V³ Флойда дешевле, да и проще; Джонсон выигрывает именно на разреженных.

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

Матрицы расстояний нужны постоянно: логистика (стоимость доставки между всеми парами складов), предподсчёт в маршрутизации, подготовка данных для задач о назначениях и коммивояжёре. Если граф большой и разреженный, а веса бывают отрицательными (скидки, компенсации, субсидии), Джонсон - это и есть рабочий ответ. Но важнее приём: потенциал - способ изменить веса так, чтобы задача стала проще, а ответ остался прежним. Он же лежит в основе A* (следующая глава: эвристика - это потенциал), в потоках минимальной стоимости, в двойственных методах оптимизации. Увидев «отрицательные веса мешают алгоритму», стоит сразу спросить себя: нельзя ли их убрать перевзвешиванием, которое сохраняет порядок путей?

Теперь сам

Граф: x→y = 2, y→z = −3, x→z = 4. Посчитай потенциалы, перевесь рёбра и проверь, что кратчайший путь из x в z не изменился.