Алгоритм Дейкстры: кратчайшие пути с кучей за O((V + E) log V)
Elman Huseynov · 2026-10-10 ·
Короткий ответ. Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных. Веса рёбер должны быть неотрицательными. Он берёт из кучи ближайшую вершину и улучшает расстояния до её соседей. Время O((V + E) log V). Ниже сигналы в условии, код на Python, разбор шага и задача Network Delay Time.
Что делает алгоритм Дейкстры?
Есть граф, у каждого ребра вес. Нужно узнать длину кратчайшего пути от старта до каждой вершины.
Обход в ширину считает путь в рёбрах. Он работает только при одинаковых весах. Дейкстра учитывает веса, но требует, чтобы они были неотрицательными.
Идея одна: жадно брать ближайшую ещё не закрытую вершину. Её расстояние уже нельзя улучшить. Через неё пробуем улучшить соседей. Такое улучшение называют релаксацией ребра.
dijkstra(6, [[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], [[4, 3], [5, 6]], [[5, 1]], []], 0)Ищем кратчайшее расстояние от вершины 0 до каждой вершины. Все расстояния сначала ∞, вершина 0 получает 0 и попадает в кучу.
Столбики: текущее расстояние от вершины 0 до каждой вершины. Столбик во всю высоту значит, что до вершины ещё не дошли.
Одна операция: одна проверка ребра или один шаг внутри кучи. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(V·E)O(E log V)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Страница паттерна: когда его применять и шаблон на шести языках
По каким словам в задаче узнать алгоритм Дейкстры?
- «Кратчайший путь», «минимальная стоимость», «минимальное время».
- «Взвешенный граф» с неотрицательными весами.
- «Сетка, где у каждой клетки своя цена входа».
- «Сколько времени сигнал идёт до всех узлов сети».
Если все веса равны единице, хватит обхода в ширину. Если есть отрицательные веса, нужен Беллман-Форд. Дейкстра лежит между ними. На собеседованиях это самый частый алгоритм на взвешенных графах.
Как работает алгоритм по шагам?
- Расстояние до старта 0, до остальных бесконечность.
- Кладём в кучу пару (0, старт).
- Снимаем с кучи пару с наименьшим расстоянием. Если оно больше уже известного, пропускаем.
- Для каждого соседа считаем новое расстояние. Если оно меньше записанного, обновляем и кладём в кучу.
- Куча пуста, все расстояния готовы.
Проверка «больше известного» это ленивое удаление. В куче лежат устаревшие пары, и мы их просто пропускаем.
Каждое ребро релаксируется один раз, каждая вершина снимается с кучи не больше раза с актуальным расстоянием. Отсюда и берётся оценка O((V + E) log V).
Как это выглядит на примере?
Вершины A, B, C, D. Рёбра: A-B вес 1, A-C вес 4. Ещё B-C вес 2 и C-D вес 1. Старт A.
Снимаем A с расстоянием 0. Сосед B получает 1, сосед C получает 4. Снимаем B с расстоянием 1. Через B до C выходит 3, это меньше 4, обновляем. Снимаем C с расстоянием 3. D получает 4. Снимаем старую пару (4, C), она устарела, пропускаем. Снимаем D. Ответ: A 0, B 1, C 3, D 4.
Как написать алгоритм Дейкстры на Python?
import heapq
def dijkstra(graph, start):
# graph: {вершина: [(сосед, вес), ...]}
dist = {v: float("inf") for v in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, v = heapq.heappop(heap)
if d > dist[v]:
continue # устаревшая запись
for u, w in graph[v]:
nd = d + w
if nd < dist[u]:
dist[u] = nd
heapq.heappush(heap, (nd, u))
return distЧтобы восстановить сам путь, храните массив prev. При каждом улучшении записывайте prev[u] = v. Потом идите от цели назад.
Чем алгоритм Дейкстры отличается от соседних алгоритмов?
| Алгоритм | Веса | Время | Когда брать |
|---|---|---|---|
| Обход в ширину | Все равны | O(V + E) | Число шагов, лабиринт |
| Дейкстра | Неотрицательные | O((V + E) log V) | Дороги, задержки, цены |
| Беллман-Форд | Любые | O(V · E) | Есть отрицательные рёбра |
| Флойд-Уоршелл | Любые | O(V³) | Между всеми парами, граф маленький |
Как решить Network Delay Time?
Дано n узлов, список рёбер (откуда, куда, время) и стартовый узел. Нужно время, за которое сигнал дойдёт до всех.
Строим список смежности, запускаем Дейкстру из старта. Ответ это максимум по всем расстояниям. Если хоть одно осталось бесконечным, сигнал не дойдёт, возвращаем -1.
На каких ошибках ломается решение?
- Запускают алгоритм на отрицательных весах. Ответ будет неверным без предупреждения.
- Не пропускают устаревшие пары. Код остаётся верным, но работает медленнее.
- Кладут в кучу (вершина, расстояние) вместо (расстояние, вершина). Куча сортирует по первому полю.
- Помечают вершину закрытой при добавлении в кучу, а не при снятии.
Как объяснить алгоритм Дейкстры на собеседовании?
Скажите: взвешенный граф, веса неотрицательные, нужны кратчайшие пути от одной вершины. Назовите кучу и жадный выбор ближайшей вершины. Назовите время O((V + E) log V).
Дальше объясните, почему жадность верна. Веса неотрицательны, поэтому обходной путь до ближайшей вершины короче быть не может. Это главный вопрос, который задают следом.
Отработать узнавание алгоритма можно на странице алгоритм Дейкстры. Обход без весов разобран на странице обход графа BFS / DFS.
Вопросы и ответы
Почему Дейкстра не работает с отрицательными весами?
Закрытая вершина считается окончательной. Отрицательное ребро может потом сделать путь до неё короче. Алгоритм этого уже не увидит.
Где алгоритм Дейкстры встречается в реальных системах?
В навигаторах: перекрёстки это вершины, дороги это рёбра, вес это время проезда. В сетевых протоколах, где маршрутизатор ищет самый дешёвый путь к соседям. В планировщиках, где вес это цена операции.
Нужно ли множество посещённых вершин?
Нет, проверки d больше dist[v] достаточно. Множество можно завести для ясности, но результат тот же.
Как восстановить сам путь, а не только длину?
Заведите словарь prev. При каждом улучшении расстояния до u запишите prev[u] = v. В конце идите от цели по prev до старта и разверните список. Это добавляет O(V) памяти.
Как найти кратчайший путь в сетке с ценами клеток?
Клетка это вершина, соседи это четыре клетки вокруг. Вес ребра это цена клетки, куда входим. Дальше тот же код.