Алгоритм Джонсона

Электромобиль едет по улицам Алматы. На подъёме он тратит энергию, на спуске часть её возвращает: мотор работает генератором и заряжает батарею. Город поднимается к горам на полкилометра, и на крутых спусках машина получает больше энергии, чем тратит на саму дорогу. В модели ниже таких участков 1346 из 20 846: у них вес отрицательный. Алгоритм Дейкстры на таком графе ошибается, Беллман — Форд справится, но медленно, а если нужны маршруты между многими парами — совсем медленно. Алгоритм Джонсона один раз считает Беллманом — Фордом потенциалы, переписывает веса так, чтобы ни один не был отрицательным, и дальше работает обычный Дейкстра.

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

Идея

Припишем каждой вершине число p(v) — потенциал — и заменим вес каждого ребра на w(u, v) + p(u) − p(v). Вес любого пути из s в t изменится на одно и то же число p(s) − p(t), поэтому кратчайшие пути останутся кратчайшими. Если подобрать потенциалы так, чтобы все новые веса стали неотрицательными, по ним можно запускать Дейкстру. Такие потенциалы даёт один запуск Беллмана — Форда.

Модель электромобиля массой 1800 кг простая. Метр ровной дороги стоит 150 мВт·ч, то есть 150 Вт·ч на километр. Подъём на метр требует mgh = 1800 · 9,81 · 1 Дж ≈ 4,9 Вт·ч, а привод с КПД 90 % тратит на это 5,45 Вт·ч. Спуск на метр возвращает 60 % от mgh — 2,94 Вт·ч. Улица длиной ℓ метров с перепадом Δh стоит 0,15ℓ + 5,45Δh Вт·ч вверх и 0,15ℓ − 2,94Δh вниз. Если спуск круче примерно 5 %, второе число отрицательное. Высоты перекрёстков — из радарной съёмки SRTM; половина участков улиц в данных круче 2 %, каждый десятый — круче 5,7 %.

Почему перевзвешивание ничего не портит

Назовём приведённым весом ребра число w′(u, v) = w(u, v) + p(u) − p(v).

Остаётся найти такие потенциалы, чтобы все приведённые веса стали неотрицательными. Добавим в граф новую вершину q и проведём из неё ребро веса 0 в каждую вершину. Если отрицательных циклов в графе нет, из q до каждой вершины есть кратчайшее расстояние δ(v) — его и находит Беллман — Форд.

Отсюда и весь алгоритм: Беллман — Форд один раз, приведённые веса, Дейкстра от каждой нужной вершины и обратный пересчёт — к найденному расстоянию прибавить p(t) и вычесть p(s). Если Беллман — Форд нашёл цикл отрицательного веса, кратчайших путей нет, и алгоритм на этом останавливается. На улицах Алматы Беллман — Форд сходится за 41 раунд; после перевзвешивания наименьший вес ребра — ровно 0, отрицательных нет.

Потенциал, который виден заранее

У электромобиля есть потенциал, который не нужно искать: высота. Возьмём p(v) = 2,94 · h(v) Вт·ч — сколько энергии возвращает спуск с высоты h. Тогда приведённый вес подъёма на Δh — 0,15ℓ + 5,45Δh − 2,94Δh = 0,15ℓ + 2,51Δh, а спуска — 0,15ℓ − 2,94Δh + 2,94Δh = 0,15ℓ. В приведённых весах спуск стоит столько же, сколько ровная дорога, а подъём — дороже на то, что рекуперация никогда не вернёт.

Листинг проверяет и это: с потенциалом 294 мВт·ч на дециметр высоты наименьший приведённый вес — 150, метр ровной дороги. Потенциал Беллмана — Форда и потенциал-высота разные, но оба годятся: приведённые веса у них разные, а кратчайшие пути и расстояния после обратного пересчёта — одни и те же. Знание задачи экономит Беллмана — Форда целиком — на этом построена первая задача ниже.

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

Отрицательный цикл — вечный двигатель

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

Подъём стоит 5,45 Вт·ч на метр, потому что привод тратит больше, чем mgh. Двигайте долю, которую возвращает спуск. Пока спуск возвращает не больше 5,45 Вт·ч на метр — до 111 % от mgh, — отрицательных циклов нет, и Беллман — Форд сходится. Выше — физически невозможная машина, которая на спуске получает больше, чем потратила на подъём, и цикл появляется: проехать по улице туда и обратно становится выгодно, если она достаточно крута. Первым, при 130 %, ломается кусок улицы в два метра, на котором SRTM показывает метровый перепад: съёмка с шагом в 30 метров на таких кусках ошибается. Беллман — Форд замечает цикл, потому что расстояния не перестают уменьшаться, а по указателям «откуда пришли» цикл и восстанавливается.

Код

Листинг строит граф улиц с энергией в целых милливатт-часах, считает потенциалы Беллманом — Фордом, проверяет, что приведённые веса неотрицательны и что высота тоже подходит в потенциалы, и строит таблицу энергии между пятью местами — пять запусков Дейкстры. В конце — самый короткий и самый экономный маршрут от Центрального стадиона вниз к Зелёному базару.

Таблица несимметрична. От площади Республики до Центрального стадиона, вниз на 49 метров, — 274 Вт·ч, обратно — 685. От Кок-Тобе до вокзала Алматы-2 машина спускается на 174 метра и тратит 1148 Вт·ч, а обратный путь стоит 2608. Самый короткий путь от стадиона к базару — 5,71 км с подъёмами на 47 метров и 810 Вт·ч; самый экономный чуть длиннее, 5,75 км, поднимается только на 18 метров и тратит 742 Вт·ч — на 8 % меньше.

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

Выигрыш тем больше, чем реже граф. На плотном графе, где E ≈ V², Джонсон и Флойд — Уоршелл сравнимы, и Флойд — Уоршелл проще. А если ответы нужны не для всех пар, а для нескольких источников, Джонсон платит только за них: Беллман — Форд один раз, Дейкстра — столько раз, сколько источников. Память — O(V + E) на граф и потенциалы; таблица всех пар — отдельные O(V²).

Где ещё работают потенциалы

Потоки и назначения. Алгоритм поиска потока наименьшей стоимости по кратчайшим путям после каждого шага пересчитывает потенциалы, чтобы в остаточной сети не появлялись отрицательные рёбра, — так сделали Джек Эдмондс и Ричард Карп в 1972 году. Ровно этот механизм работает в венгерском алгоритме: его потенциалы курьеров и заказов — те же числа p.

A* и ориентиры. Эвристика A* — потенциал; метод ALT вычисляет его по расстояниям до нескольких ориентиров и неравенству треугольника.

Графы без циклов. Если граф ациклический, отрицательные веса не страшны вовсе: кратчайшие пути находятся одним проходом в топологическом порядке, без Беллмана — Форда и без Дейкстры.

Пути, которые меняются. Когда веса немного меняются, старые потенциалы часто остаются почти правильными: после пересчёта отрицательных рёбер мало, и потенциалы чинят точечно, не запуская Беллмана — Форда заново.

История

Перевзвешивание по потенциалам появилось в задачах о потоках: в несколько другом виде — у Делберта Фалкерсона в 1961 году, затем у Нобуаки Томидзавы в 1971-м и у Эдмондса и Карпа в 1972-м. Дональд Джонсон применил его к кратчайшим путям между всеми парами — сначала в отчёте 1973 года, затем в статье «Efficient algorithms for shortest paths in sparse networks» 1977 года, где сам ссылался на работу Эдмондса и Карпа. Название «алгоритм Джонсона» закрепилось за сочетанием: один Беллман — Форд, перевзвешивание и Дейкстра от каждой вершины.

Задачи

В первой задаче потенциал не нужно искать: он дан в условии в виде высот, и Беллман — Форд на таком графе не уложился бы во время. Во второй — настоящий алгоритм Джонсона на графе с произвольными отрицательными весами.