Алгоритм Дейкстры: как работает и где используется

Q: В чём разница между алгоритмом Дейкстры и поиском в ширину (BFS)?

BFS (поиск в ширину) находит кратчайший путь только в невзвешенных графах, считая количество рёбер. Алгоритм Дейкстры работает с взвешенными графами — он учитывает веса рёбер и находит путь с минимальной суммарной стоимостью. BFS работает за O(n + m), тогда как Дейкстра — за O(n² + m) или O((n + m) log n) с кучей. Если веса всех рёбер равны 1, Дейкстра эквивалентен BFS.

Алгоритм Дейкстры — один из классических алгоритмов на графах. Разбираем принцип работы, реализацию на C++, сложность и практическое применение.

Дарья Закаулова

6 июня 2024, 16:30, отредактировано 3 апреля 2026, 14:00

Обложка: Алгоритм Дейкстры: как работает и где используется

Зачем нужен этот алгоритм

Алгоритм Дейкстры — это алгоритм на графах для нахождения кратчайших путей от заданной вершины до всех остальных вершин во взвешенном графе с неотрицательными весами рёбер, предложенный нидерландским математиком Эдсгером Дейкстрой в 1956 году. Алгоритм Дейкстры используют для решения «задачи о кратчайших путях с единственным источником». Она заключается в поиске кратчайших путей от заданной вершины до всех остальных во взвешенном графе с неотрицательными весами.

Ключевые выводы

Алгоритм Дейкстры — классический алгоритм нахождения кратчайших путей от одной вершины до всех остальных во взвешенном графе с неотрицательными весами рёбер.

Сложность простейшей реализации — O(n² + m), с очередью приоритетов (двоичной кучей) — O((n + m) log n), что делает алгоритм эффективным на разреженных графах.

Алгоритм не работает с отрицательными весами рёбер. Для таких задач используют алгоритм Беллмана-Форда (сложность O(nm)) или алгоритм Джонсона.

Применяется в навигации (Google Maps, GPS), маршрутизации в компьютерных сетях (OSPF), робототехнике, системах бронирования и игровых движках.

Для закрепления материала рекомендуем порешать задачи на acmp.ru — ссылки на практические задачи приведены в конце статьи.

Далее будем использовать следующие обозначения, описывающие характеристики графа:

n — количество вершин в графе;
m — количество ребер в графе;
s — стартовая вершина.

Алгоритм Дейкстры выполняется за n итераций. На каждой итерации выбирается вершина v с минимальным значением d[v] среди непомеченных вершин. Эта вершина v затем отмечается как помеченная.

Далее на текущей итерации происходит этап релаксации. В этом этапе просматриваются все ребра (v, to), исходящие из вершины v, и проверяется, можно ли улучшить значение d[to].

То есть, если длина рассматриваемого ребра равна l, тогда d[to] = min(d[to], d[v] + l). При успешной релаксации, то есть когда удалось улучшить расстояние до вершины to, в массиве p указывается, что предшественником на кратчайшем пути к вершине to является вершина v, то есть p[to] = v.

На этом итерация заканчивается.

По завершении n итераций все вершины графа оказываются помеченными, и алгоритм заканчивает выполнение.

Важно заметить, что если из начальной вершины s невозможно построить путь до некоторых вершин графа, их значения d[v] останутся бесконечными. Алгоритм можно завершить досрочно, как только будет выбрана вершина с бесконечным значением расстояния.

Рассмотрим работу алгоритма на примере. Будем искать кратчайшие пути от вершины 4.

Изначально массивы u (посещений), d (расстояния) и p (предков) для графа из примера имеют следующие значения:

Алгоритм Дейкстры: как работает и где используется_13

Изначальные значения

На первой итерации мы выбираем вершину v с наименьшим значением d[v]. Очевидно, что на первом шаге будет выбрана стартовая вершина — 4.

Помечаем её посещённой u[4] = true.

Дальше проходим по всем соседям вершины 4 и пытаемся улучшить для них значения в массиве d. Для всех вершин, расстояние до которых удалось улучшить, в список предков записываем вершину 4. На первой итерации удалось улучшить расстояния до вершин 1, 5, 6. В результате значения массивов u, d, p изменились следующим образом:

Алгоритм Дейкстры: как работает и где используется_17

После первой итерации

На следующем шаге выбираем вершину 6. Улучшаем расстояния до вершин 3 и 7.

Алгоритм Дейкстры: как работает и где используется_19

После второй итерации

Следующая непосещённая вершина с минимальным весом — 1.

Расстояние от вершины 4 до вершины 1 равняется 3. Пытаемся улучшить расстояние до всех её соседей. Так, например, можно улучшить расстояние до вершины 5. Ранее оно было равно 8, а после релаксации это значение уменьшается:

d[5] = min(d[5], d[1] + l) = min(8, 3 + 2) = 5.

Алгоритм Дейкстры: как работает и где используется_23

После третьей итерации

И аналогичным образом мы проходим все оставшиеся итерации.

Выбираем непосещённую вершину с минимальным значением d[v]. На этой итерации будет выбрана вершина 7. Ни для одного её соседа длину кратчайшего пути улучшить не удалось.

Алгоритм Дейкстры: как работает и где используется_26

После четвёртой итерации

На следующей итерации будет посещена вершина 2. От неё удалось улучшить путь до вершин 0 и 3.

Алгоритм Дейкстры: как работает и где используется_28

После пятой итерации

Далее посетив вершину 5 улучшаем путь до вершины 8.

Алгоритм Дейкстры: как работает и где используется_30

После шестой итерации

На последующих итерациях помечаются посещёнными вершины 8, 0 и 3. От них нельзя улучшить путь ни до одного из их соседей.

Алгоритм Дейкстры: как работает и где используется_32

После седьмой итерации

Алгоритм Дейкстры: как работает и где используется_33

После восьмой итерации

Алгоритм Дейкстры: как работает и где используется_34

После девятой итерации

После окончания работы алгоритма значения массивов u, d, p:

Алгоритм Дейкстры: как работает и где используется_36

После десятой итерации

Реализация на C++

			vector <vector <pair <long long, long long> >> vP(n); // список смежности

vector <long long> d(n, INT_MAX); // кратчайшие пути
vector <long long> p(n, -1); // предки
vector <bool> used(n); // посещенные вершины

d[s] = 0; // обнуляем кратчайший путь для стартовой вершины
    
for (long long i = 0; i < n; i++) {
    long long v = -1;
    // Находим не посещенную вершину с минимальным d[j]
    for (long long j = 0; j < n; j++) {
        if (!used[j] && (v == -1 || d[j] < d[v])) {
            v = j;
        }
    }
    
    // Если расстояние до выбранной вершины равняется ∞, то выходим из алгоритма.
    if (d[v] == INT_MAX) {
        break;
    }
    // Отмечаем вершину v посещенной
    used[v] = true;
    
    // Проводим релаксацию. 
    for (long long j = 0; j < vP[v].size(); j++) { // Проходим по всем соседям выбранной вершины
        long long to = vP[v][j].first, l = vP[v][j].second;
        if (d[to] > d[v] + l) { // Проверяем, можно ли улучшить расстояния до соседа
            d[to] = d[v] + l; 
            p[to] = v;
        }
    }
}

Оценим скорость работы алгоритма. Он состоит из n итераций, внутри каждой из которых осуществляется поиск вершины с наименьшим значением d[v] (при простейшей реализации n итераций). Также за время работы алгоритма m раз производится попытка релаксации.

Таким образом асимптотика алгоритма равняется O(n^2+m).

С учётом оценки скорости работы алгоритма очевидно, что на его производительность влияет плотность графа. Так, например, для разреженных графов (с относительно небольшим числом рёбер по сравнению с числом вершин) алгоритм Дейкстры в стандартной реализации будет не очень эффективен. Но это можно исправить, ускорив операцию поиска минимального элемента использованием двоичных куч. Тогда время работы алгоритма можно сократить до O(n log n + m).

Где используется

Этот алгоритм универсален, поэтому его можно использовать в разных сферах.

Например, в навигационных системах и картографии алгоритм Дейкстры может помочь проложить маршрут для пешеходов или автомобилей, избегая пробок и выбирая оптимальные дороги.

В робототехнике этот алгоритм применяется для планирования движения роботов, чтобы они могли перемещаться в пространстве используя кратчайшие пути и обходя препятствия.

В системах бронирования для поиска наиболее быстрых и дешевых билетов с учетом возможных пересадок.

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

Ограничения

Основным ограничением алгоритма является невозможность работы с отрицательными весами рёбер, так как в этом случае возможны циклы с отрицательной суммой весов, что приведет к бесконечным попыткам уменьшения длины пути.

Из-за своей большой временной сложности алгоритм Дейкстры в стандартной реализации может быть не очень эффективен для больших графов, поэтому на практике часто используют разные эмпирические улучшения, с учетом специфики задачи. Также стоит отметить, что для больших графов также требуется выделение значительных ресурсов памяти.

Алгоритм Дейкстры не приспособлен для работы с динамически изменяющимися графами. То есть если во время работы алгоритма изменятся значения весов, то в итоге вы скорее всего получите неверные результаты.

Какие еще есть алгоритмы для поиска кратчайшего пути

Алгоритм Беллмана-Форда вычисляет кратчайшие пути от одной вершины ко всем остальным, но в отличие от алгоритма Дейкстры, способен работать с графами, имеющими рёбра с отрицательными весами. Его временная сложность составляет O(nm). Для графов с большим числом рёбер этот алгоритм может работать медленнее, чем Дейкстра. Другие алгоритмы и их применение — в нашем разделе Алгоритмы.

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин. Он комбинирует алгоритмы Дейкстры и Беллмана-Форда и имеет временную сложность O(n^2 log n + nm). Он может быть более эффективным для графов с малым количеством ребер.

Алгоритм А* — это эвристический метод поиска кратчайшего пути, который может работать быстрее, чем алгоритм Дейкстры, при условии использования хорошей эвристической функции. А* применяется в задачах маршрутизации и навигации, особенно в играх и робототехнике.

Модификации алгоритма Дейкстры для разреженных графов. Для графов с малым числом ребер относительно количества вершин можно использовать специальные оптимизации:

Алгоритм Дейкстры с очередью с двойным приоритетом. Применение специализированных структур данных, таких как очереди с двойным приоритетом, может ускорить выполнение алгоритма на разреженных графах.
Алгоритм Дейкстры с помощью дек (deque). Это улучшение алгоритма Дейкстры для разреженных графов, использующее дек для более эффективного управления очередью вершин.

Алгоритм Флойда-Уоршелла предназначен для нахождения кратчайших путей между всеми парами вершин. Его временная сложность составляет O(n^3), что делает его менее эффективным для очень больших графов, но он может быть выгодным для плотных графов с небольшим числом вершин.

Часто задаваемые вопросы

Какова сложность алгоритма Дейкстры?

Простейшая реализация алгоритма Дейкстры имеет временную сложность O(n² + m), где n — количество вершин, m — количество рёбер. Для разреженных графов эффективнее использовать реализацию с двоичной кучей (очередью с приоритетом) — тогда сложность снижается до O((n + m) log n). Пространственная сложность в обоих случаях — O(n + m).

Почему алгоритм Дейкстры не работает с отрицательными весами?

Алгоритм Дейкстры основан на жадном принципе: однажды помеченная вершина считается окончательно обработанной с минимальным расстоянием. При наличии рёбер с отрицательными весами это допущение нарушается — через позднюю вершину с отрицательным ребром можно получить более короткий путь к уже «закрытой» вершине. Для графов с отрицательными весами используйте алгоритм Беллмана-Форда.

В чём разница между алгоритмом Дейкстры и поиском в ширину (BFS)?

BFS (поиск в ширину) находит кратчайший путь только в невзвешенных графах, считая количество рёбер. Алгоритм Дейкстры работает с взвешенными графами — он учитывает веса рёбер и находит путь с минимальной суммарной стоимостью. BFS работает за O(n + m), тогда как Дейкстра — за O(n² + m) или O((n + m) log n) с кучей. Если веса всех рёбер равны 1, Дейкстра эквивалентен BFS.

Где применяется алгоритм Дейкстры на практике?

Алгоритм Дейкстры используется во многих реальных системах: навигация и картография — Google Maps, Яндекс.Карты и GPS-навигаторы строят маршруты именно через него; компьютерные сети — протокол OSPF (Open Shortest Path First) применяет Дейкстру для маршрутизации пакетов; робототехника — планирование пути в пространстве с препятствиями; игровая разработка — поиск пути для NPC на игровых картах.