Алгоритм Дейкстры
Ваш навигатор знает самый быстрый путь от вашей двери почти куда угодно. В основе этой идеи лежит алгоритм, который Эдсгер Дейкстра придумал примерно за двадцать минут в 1956 году: расти от старта наружу и всегда сначала завершать ближайшее место.
Идея
Представьте города, соединенные дорогами разной длины. Вопрос: какой путь из моего города до каждого другого самый короткий? Поиск в ширину отвечает на него, когда все дороги считаются одинаково, но здесь маршрут с большим числом дорог может оказаться короче. Алгоритм Дейкстры хранит для каждого города кратчайшее найденное расстояние и наращивает область городов, расстояние до которых известно точно, всегда добавляя ближайший город, расстояние до которого еще не известно точно.
Шаг за шагом
Задайте старту расстояние 0, а всем остальным вершинам — бесконечность. Поместите старт в очередь с приоритетом — очередь, которая всегда выдает вершину с наименьшим расстоянием. Возьмите эту вершину; ее расстояние теперь окончательное. Для каждого соседа, чье расстояние еще не окончательное, вычислите расстояние через эту вершину: ее расстояние плюс длина ребра. Если оно меньше текущего расстояния соседа, уменьшите его, запомните эту вершину как путь к соседу и поместите соседа в очередь. Это называется релаксацией ребра. Повторяйте, пока очередь не опустеет или пока из нее не будет взята цель.
Пример
Возьмем ребра A–B длины 4, A–C 1, B–C 2, B–D 1, C–D 5 и D–E 3 и начнем с A. Взяв A, получаем для B расстояние 4, а для C — 1. Ближе всех C, поэтому ее расстояние 1 окончательное; через C расстояние B уменьшается до 1 + 2 = 3, а D получает 1 + 5 = 6. Теперь ближе всех B, с окончательным расстоянием 3, и через B расстояние D уменьшается до 3 + 1 = 4. Расстояние D окончательно равно 4, и через D вершина E получает 4 + 3 = 7. Значит, кратчайший путь из A в E — A → C → B → D → E длины 7, хотя A → B → D → E использует меньше ребер и имеет длину 8.
Почему он верен
Пусть вершина X — ближайшая в очереди, на расстоянии d. Любой другой путь от старта к X должен в какой-то момент покинуть область вершин с окончательным расстоянием, и первая вершина, до которой он доходит вне этой области, находится в очереди, а значит, уже не ближе d. Оставшаяся часть пути не может его сократить, потому что отрицательных ребер нет. Значит, d — кратчайшее расстояние до X. С отрицательным ребром это рассуждение не работает; тогда используют алгоритм Беллмана — Форда, который релаксирует каждое ребро снова и снова.
История и применение
Эдсгер В. Дейкстра придумал алгоритм в 1956 году, чтобы показать новый компьютер ARMAC в Амстердаме, находя маршруты между городами Нидерландов, и опубликовал его в 1959 году. Та же идея, но с более умной очередью, работает в навигаторах и в протоколах маршрутизации интернета, таких как OSPF и IS-IS, которые вычисляют кратчайший путь данных между маршрутизаторами. Поиск A* добавляет оценку оставшегося расстояния, поэтому может двигаться к цели и просматривать меньше вершин.
Попробуйте сами
Откройте приложение и нажмите Шаг. Числа на ребрах — их длины, а число на каждой вершине — ее расстояние на данный момент. Вершины в очереди синие, окончательные — зеленые, а очередь под графом перечисляет их с расстояниями, ближайшие первыми. Следите за моментами, когда расстояние уменьшается, потому что маршрут, который выглядел длиннее, оказывается короче, и выберите цель, чтобы увидеть, как поиск останавливается, как только расстояние до цели становится окончательным.
Часто задаваемые вопросы
Какова временная сложность алгоритма Дейкстры?
Она зависит от очереди с приоритетом. С простым списком — O(V²) для V вершин; с двоичной кучей — O((V + E) log V) для E ребер; с фибоначчиевой кучей — O(E + V log V), как показали Майкл Фредман и Роберт Тарьян в 1984 году.
Работает ли алгоритм Дейкстры с отрицательными весами ребер?
Нет. Он предполагает, что расстояние вершины уже не может улучшиться, когда она стала ближайшей в очереди, а отрицательное ребро может это нарушить. Для графов с отрицательными ребрами используйте алгоритм Беллмана — Форда.
Находит ли алгоритм Дейкстры путь до каждой вершины?
Да. Если довести его до конца, он дает кратчайшее расстояние от старта до каждой достижимой вершины, а запомненные вершины образуют дерево кратчайших путей. Если нужен только один путь, ранняя остановка, когда расстояние до цели окончательное, экономит работу.
Как алгоритм Дейкстры связан с A*?
Поиск A* — это алгоритм Дейкстры с подсказкой: он упорядочивает очередь по сумме текущего расстояния и оценки оставшегося расстояния, например расстояния по прямой на карте. С хорошей оценкой он находит тот же кратчайший путь, просматривая гораздо меньше вершин.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробуйте алгоритм Дейкстры