Алгоритм Дейкстры
Также: Dijkstra's algorithm · SPF · кратчайшие пути из одной вершины
Как навигатор находит кратчайший путь, не перебирая миллионы маршрутов: волна идёт от старта, и каждый раз ближайший ещё не посещённый перекрёсток получает окончательное расстояние. Алгоритм придуман за двадцать минут на террасе кафе в 1956 году и до сих пор считает маршруты в интернете.
Вы стоите на площади Республики и хотите дойти до Зелёного базара. Навигатор отвечает за долю секунды: 3,8 километра. Он не перебирал маршруты: на семи тысячах перекрёстков их столько, что не хватило бы никакого времени. Он пустил по улицам волну и остановился, когда волна докатилась до базара. Посмотрите сами: это настоящий Алматы из OpenStreetMap, и волна — настоящий алгоритм Дейкстры. Нажмите на карту, чтобы перенести финиш, и на кнопку A, чтобы перенести старт.
Посмотрите, как растёт волна: не кругом, а вдоль улиц, быстро по длинным проспектам и медленно в кварталах, где дорога петляет. Цвет показывает расстояние от старта по дорогам. Когда волна касается финиша, путь готов, и он кратчайший — не «хороший», не «примерно лучший», а самый короткий из всех возможных. Почему это гарантировано, разберём ниже.
Идея
Если все дороги имеют неотрицательную длину, то ближайший к старту из ещё не посещённых перекрёстков уже не станет ближе. Любой другой путь к нему проходит через перекрёсток, который дальше, а дальше — значит длиннее. Поэтому его расстояние можно записать окончательно и разослать соседям.
Из этой одной мысли получается весь алгоритм. Для каждого перекрёстка храним лучшее известное расстояние: у старта ноль, у остальных бесконечность. Дальше повторяем:
- берём перекрёсток с наименьшим известным расстоянием среди ещё не посещённых и объявляем его расстояние окончательным;
- для каждой улицы, которая из него выходит, проверяем: не короче ли дойти до соседа через этот перекрёсток? Если короче — записываем новое расстояние.
Второй шаг называется релаксацией ребра — слово из старых работ по оптимизации, где «ослабляли» завышенную оценку. Первый шаг требует быстро находить минимум среди меняющихся чисел, и для этого есть готовая структура — двоичная куча.
Как это работает по шагам
Возьмём маленький кусок того же города — квартал у площади Республики — и пройдём медленно. На каждом перекрёстке подписано текущее расстояние в метрах. Синие цифры окончательные: эти перекрёстки уже достали из кучи. Оранжевые — предварительные: такой путь найден, но, может быть, найдётся короче. Внизу — содержимое кучи, по возрастанию.
Пощёлкайте «шаг вперёд» и проследите за кучей. Перекрёсток, до которого нашли путь в самом начале, может долго пролежать в ней, пока вокруг обрабатываются места поближе. Зато когда он окажется наверху, это будет означать: все более близкие места уже обработаны, и ничего короче не найдётся.
Обратите внимание ещё на одно: одно и то же место может попасть в кучу несколько раз — сначала с одним расстоянием, потом, через другую улицу, с меньшим. Мы не ищем старую запись, чтобы её исправить, а просто кладём новую. Старая всплывёт позже и будет пропущена, потому что к тому времени место уже обработано. Этот приём называют ленивым удалением, и он делает код проще почти без потерь в скорости.
Почему ответ верный
Если длины всех рёбер неотрицательны, то в момент, когда вершину u достают из кучи, записанное расстояние dist[u] равно длине кратчайшего пути от старта до u.
Предположим противное, и пусть u — первая вершина, которую достали с неверным расстоянием: dist[u] больше длины кратчайшего пути δ(u). Возьмём какой-нибудь кратчайший путь от старта до u. Он начинается в обработанной вершине (старт обработан первым), а кончается в необработанной u, значит, где-то на нём есть первая необработанная вершина y, а перед ней — обработанная x.
Когда обрабатывали x, её расстояние было верным (u — первая ошибка), и ребро (x, y) прошло релаксацию. Поэтому dist[y] ≤ δ(x) + w(x, y) = δ(y): кусок кратчайшего пути сам кратчайший. Дальше от y до u по тому же пути идут рёбра неотрицательной длины, значит δ(y) ≤ δ(u) < dist[u].
Получили dist[y] < dist[u], но куча выдала u, а не y, то есть dist[u] ≤ dist[y]. Противоречие.
Перечитайте второй абзац: неотрицательность рёбер нужна ровно в одном месте — там, где мы сказали «дальше по пути значит не короче». Уберите её, и доказательство рассыпается. А вместе с ним и алгоритм.
Ловушка: отрицательная дорога
Отрицательных дорог в городе не бывает, но в графах они встречаются постоянно: скидка за проезд, выигрыш в обмене валют, энергия, которую электромобиль возвращает на спуске. Подвигайте ползунок: дорога C → B становится всё «короче», и на значении −3 Дейкстра начинает врать.
Что произошло: B достали из кучи с расстоянием 2 и объявили окончательным. Потом обработали C (расстояние 4) и обнаружили, что через C до B можно добраться за 4 − 3 = 1. Но B уже закрыта, а ошибка успела уехать дальше — в D. Для графов с отрицательными рёбрами есть алгоритм Беллмана — Форда: он медленнее, зато не делает преждевременных выводов.
Частая ошибка — «починить» Дейкстру, прибавив ко всем рёбрам одну и ту же константу, чтобы они стали положительными. Это меняет ответ: путь из пяти рёбер подорожает на пять констант, а путь из двух — на две, и короткий по числу рёбер маршрут незаслуженно выиграет. Правильный способ переписать веса есть, он называется потенциалами (так работает алгоритм Джонсона), но константа — не он.
Код
Граф хранится списками смежности: для каждой вершины — список пар «сосед, длина дороги». Куча — стандартная: heapq в Python и container/heap в Go. Ни там, ни там нет операции «уменьшить ключ», и ленивое удаление здесь очень кстати.
Восстановить сам маршрут помогает массив parent: когда релаксация улучшает расстояние до v, мы запоминаем, откуда пришли. От финиша идём по этим ссылкам назад до старта и переворачиваем список.
А теперь тот же алгоритм на всём городе. Файл с графом лежит на сервере, где исполняется код, и программа читает его, как читала бы любые данные. Запустите обе версии и сравните время: Go быстрее Python в несколько раз на одном и том же сервере.
Обратите внимание на строку с break: если нужен путь до одного финиша, искать дальше бессмысленно. Волна, которая дошла до базара, осмотрела 1422 перекрёстка из 7909. Без раннего выхода алгоритм обойдёт весь город.
Сколько это стоит
Обозначим число перекрёстков V, число улиц E. Каждую вершину обрабатывают один раз, и при этом смотрят на её рёбра, так что всего рёбер просмотрено O(E). Каждое успешное улучшение кладёт запись в кучу, а записей в куче не больше, чем рёбер, и операция с кучей стоит O(log E) = O(log V). Итого:
| Чем искать минимум | Время | Когда лучше |
|---|---|---|
| просмотр всего массива (так в статье 1959 года) | O(V²) | плотные графы, где E близко к V² |
| двоичная куча | O((V + E) log V) | дороги, сети, почти всё на практике |
| фибоначчиева куча | O(E + V log V) | теоретически лучшая оценка; на практике обычно медленнее двоичной |
Дорожные графы разреженные: в нашем Алматы E ≈ 1,3 V, у перекрёстка в среднем меньше трёх улиц. Для них куча выигрывает с огромным запасом. Ниже замер на квадратных решётках разного размера: две реализации, массив и куча, на одном сервере. Оси логарифмические, поэтому степенной рост выглядит прямой линией, и её наклон показывает степень.
Наклон версии с массивом близок к 2: удвоили город — время выросло вчетверо. Версия с кучей растёт чуть быстрее линейного. На городе в миллион перекрёстков разница — это секунды против часов.
Как навигаторы успевают быстрее
Дорожный граф целой страны — десятки миллионов вершин, и даже хорошая куча не даёт ответ за миллисекунды. Вернитесь к первой сцене и переключите режим.
- A* добавляет к расстоянию подсказку — расстояние по прямой до финиша — и тянет волну в нужную сторону. От площади Республики до Зелёного базара он осматривает 209 перекрёстков вместо 1422. Подробности — в статье про A*.
- Поиск навстречу пускает две волны, от старта и от финиша, и останавливается, когда они встретились. Две волны радиуса r/2 покрывают заметно меньше, чем одна радиуса r: на том же маршруте 769 перекрёстков. Подробнее — двунаправленный поиск.
- Предподсчёт. Настоящие навигаторы заранее, один раз, перерабатывают граф: например, строят иерархии сжатия, добавляя «короткие пути через неважные улицы». После этого запрос по графу континента занимает миллисекунды. Внутри у всех этих методов — тот же Дейкстра, только на хитро подготовленном графе.
Переключите и «Быстрее»: вместо метров алгоритм складывает секунды при условных скоростях — проспекты быстрее дворов. Маршрут может стать длиннее по расстоянию и всё равно выиграть по времени. Алгоритму всё равно, что складывать, лишь бы складываемое было неотрицательным.
Двадцать минут на террасе
В 1956 году Эдсгер Дейкстра работал в Математическом центре, и ему нужно было показать публике новую вычислительную машину ARMAC. Задачу он искал такую, чтобы её понял человек без всякой подготовки, и выбрал кратчайший путь между городами — на упрощённой карте из 64 городов, чтобы номер города помещался в шесть бит.
Много лет спустя, в интервью 2001 года, он вспоминал, что придумал алгоритм за двадцать минут: однажды утром ходил с невестой по магазинам, они устали и присели выпить кофе на террасе кафе. Ни карандаша, ни бумаги при нём не было, и Дейкстра потом считал это удачей: без бумаги поневоле избегаешь всех сложностей, без которых можно обойтись. Статья вышла только в 1959 году и заняла три страницы — «A note on two problems in connexion with graphs». Во второй её задаче — тот самый алгоритм, в первой — построение минимального остовного дерева.
В исходной статье минимум искали просмотром массива, отсюда O(V²). Кучи появились в алгоритме позже, и для разреженных графов это изменило всё.
Задачи
Первая — Дейкстра в чистом виде, с восстановлением пути. Во второй стартов много, а волна одна. В третьей придётся слегка изменить сам граф: состояние «где я» превратится в «где я и потратил ли купон».
Маршрут курьера Пожарные части Один бесплатный проездДанные: Дороги Алматы © участники OpenStreetMap, ODbL