Алгоритм Дейкстры: как найти кратчайший путь в графе

Алгоритм Дейкстры - один из тех алгоритмов, которые встречаются и на курсе по дискретной математике, и на собеседовании в любую IT-компанию, и в реальных сервисах вроде Яндекс.Карт. Он находит кратчайшие расстояния от одной вершины графа до всех остальных. На словах звучит просто, но в детали обычно никто не вникает. Разберём аккуратно: на чём он работает, как именно расширяет «волну» по графу и почему ломается на отрицательных весах.

Постановка задачи

Дан взвешенный ориентированный (или неориентированный) граф G = (V, E), в котором каждому ребру (u, v) сопоставлен неотрицательный вес w(u, v) ≥ 0. Выбрана стартовая вершина s. Нужно найти d[v] - длину кратчайшего пути из s в каждую вершину v.

Под «весом» можно понимать что угодно: расстояние, время в пути, стоимость переходов, штраф. Главное - что это число, и оно неотрицательно.

Идея алгоритма

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

«Расслабить ребро (u, v)» означает: если через u до v можно дойти быстрее, чем мы знали раньше, обновляем d[v].

Ключевое наблюдение, на котором держится корректность: если все веса неотрицательны и u - вершина с минимальным d[u] среди ещё не обработанных, то улучшить d[u] уже не получится, потому что любой другой путь сюда пройдёт через ещё более далёкую вершину.

Псевдокод

function dijkstra(G, s):
    d[s] = 0
    d[v] = ∞    для всех v ≠ s
    Q = priority queue, push (0, s)

    while Q не пуста:
        (cur_dist, u) = Q.pop_min()
        if cur_dist > d[u]:           # устаревшая запись
            continue
        for каждое ребро (u, v) с весом w:
            if d[u] + w < d[v]:        # релаксация
                d[v] = d[u] + w
                Q.push((d[v], v))

    return d

Хранение «устаревших записей» - мелкий, но важный момент. Когда мы обновляем d[v], мы не вытаскиваем старое значение из очереди (это дорого), а просто кладём новое. При попе мы проверяем, не стало ли значение неактуальным.

Шаг за шагом на маленьком графе

Возьмём граф из пяти вершин A, B, C, D, E и рёбер:

A - B (вес 4)
A - C (вес 2)
B - C (вес 3)
B - D (вес 2)
B - E (вес 3)
C - B (вес 1)
C - D (вес 4)
C - E (вес 5)
D - E (вес 1)

Старт - вершина A. Сначала d[A] = 0, все остальные - ∞. Очередь: (0, A).

Шаг 1. Достаём A. Расслабляем рёбра: d[B] = 4, d[C] = 2. Очередь: (2, C), (4, B).

Шаг 2. Достаём C (минимум, равен 2). Через C: до B - 2 + 1 = 3 < 4, обновляем; до D - 2 + 4 = 6; до E - 2 + 5 = 7. Состояние: d[B] = 3, d[D] = 6, d[E] = 7. В очереди (3, B), (4, B-устаревшее), (6, D), (7, E).

Шаг 3. Достаём B (мин = 3). Через B: до D - 3 + 2 = 5 < 6, обновляем; до E - 3 + 3 = 6 < 7, обновляем. Состояние: d[D] = 5, d[E] = 6.

Шаг 4. Достаём устаревшую запись (4, B). cur_dist = 4 > d[B] = 3 - пропускаем.

Шаг 5. Достаём D (мин = 5). Через D до E: 5 + 1 = 6. Не лучше - не обновляем.

Шаг 6. Достаём E (мин = 6). Исходящих рёбер нет.

Результат:

d[A] = 0,  d[B] = 3,  d[C] = 2,  d[D] = 5,  d[E] = 6

Заметьте: жадность Дейкстры в действии - мы дважды нашли путь в B (сначала длиной 4, потом 3) и переоценили его, как только нашёлся более короткий. Но как только вершина «достата» из очереди с актуальным значением, её расстояние больше никогда не меняется.

На игрушечном графе ход алгоритма легко проследить на бумаге, но при 20+ вершинах руками уже не справиться. Опиши свой граф ниже в формате «вершина1 вершина2 вес» по строкам - собранный запрос откроет чат с пошаговой трассировкой Дейкстры: что в d[v] после каждого шага, какие рёбра расслаблялись и почему путь именно такой.

Сложность

Зависит от структуры данных под приоритетную очередь:

• С двоичной кучей (std::priority_queue в C++, heapq в Python): O((V + E) log V). Это стандарт.
• С массивом (наивно ищем минимум): O(V²). Подходит для плотных графов, где E ≈ V².
• С фибоначчиевой кучей: O(E + V log V) теоретически, на практике константа большая, почти никто не использует.

Почему не работает с отрицательными весами

Жадность Дейкстры опирается на ключевое допущение: если мы достали вершину u с минимальным текущим расстоянием, никакой путь не сделает его короче. Это верно, только если все веса ≥ 0.

Контрпример. Граф из трёх вершин:

A - B (вес 1)
A - C (вес 4)
B - C (вес -3)

Дейкстра достанет A, обновит d[B] = 1, d[C] = 4. Дальше достанет B (мин), обновит d[C] = 1 + (-3) = -2. Если бы алгоритм работал корректно, всё хорошо - но в более сложных графах он может «зафиксировать» расстояние до вершины до того, как обнаружит более короткий путь с отрицательным ребром. Поэтому в ответе появятся завышенные значения.

Если в графе есть отрицательные веса - используйте алгоритм Беллмана–Форда (медленнее, O(V·E), но корректен) или алгоритм Джонсона (для всех пар вершин: перевзвешивание + Дейкстра).

Восстановление пути, а не только расстояний

Чаще нужно знать не только длину, но и сам путь. Для этого заводят массив prev[v] - предшественника v в кратчайшем пути из s. В момент релаксации:

if d[u] + w < d[v]:
    d[v] = d[u] + w
    prev[v] = u
    Q.push((d[v], v))

Чтобы восстановить путь до t, идём от t назад: t → prev[t] → prev[prev[t]] → ... → s и разворачиваем.

Где применяется

• Маршрутизация в сетях. Протокол OSPF использует Дейкстру для построения таблиц маршрутизации.
• Игры и навигация. Поиск пути на тайловой карте - частный случай взвешенного графа, где веса учитывают тип местности.
• Картографические сервисы. Дейкстра - основа базового маршрутизатора в Яндекс.Картах и Google Maps. В реальности её ускоряют двунаправленным поиском, A* и предварительной иерархизацией дорог, но идея - Дейкстра.
• Сетевая аналитика. В социальных и логистических сетях - оценка «расстояний» по любым неотрицательным метрикам.

Частые ошибки

• Игнорируют устаревшие записи в приоритетной очереди - алгоритм обрабатывает одну вершину несколько раз, и сложность из логарифмической превращается в квадратичную.
• Запускают на графе с отрицательными весами и удивляются неверным результатам.
• Путают с BFS. BFS даёт кратчайший путь только в невзвешенном графе. Если все веса равны 1, BFS и Дейкстра совпадают, но BFS работает быстрее: O(V + E).
• Считают, что Дейкстра ищет путь от одной пары вершин. На самом деле он находит расстояния от старта до всех вершин одновременно. Если нужна только одна пара, можно ранне остановиться, как только нужная вершина достата из очереди.

FAQ

Можно ли использовать Дейкстру на неориентированном графе? Да. Неориентированный граф представляется как ориентированный с двумя дугами на каждое ребро - (u, v) и (v, u) с одинаковыми весами.

Что если граф разрежен - миллион вершин, но мало рёбер? Стандартная Дейкстра с кучей справится: сложность зависит от E, а не от V².

Чем A* принципиально отличается? A* - это Дейкстра + эвристика, оценивающая остаток до цели. Когда эвристика согласована (h(u) ≤ w(u, v) + h(v)), A* корректен и быстрее: меньше вершин раскрывается. Если эвристика тождественно нулевая, A* совпадает с Дейкстрой.

Коротко

Алгоритм Дейкстры - жадный обход взвешенного графа с приоритетной очередью. Работает только при неотрицательных весах, даёт расстояния от стартовой вершины до всех остальных за O(E log V). Если в графе есть отрицательные рёбра - берите Беллмана–Форда. Если нужно ускорение для конкретной цели - A*. Для других задач на орграфах - например, поиска сильно связных компонент - пригодится алгоритм Тарьяна.