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

В уроке про BFS мы уже построили два массива: dist для расстояний и parent для восстановления пути. Там единица веса была зашита в саму структуру обхода — каждый шаг стоил одно ребро. Теперь рёбра имеют разные веса, и BFS теряет смысл: нельзя просто считать слои. Дейкстра решает ту же задачу кратчайших путей, но опирается на приоритетную очередь, с которой мы работали в уроке про heapq. Оба инструмента уже в руках — осталось собрать их вместе правильно.

Контракт графа и инициализация dist[], parent[]

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

Граф передаётся как словарь adj, где каждый ключ — вершина, а значение — список пар (v, w): сосед и вес ребра. Важное требование: все вершины должны быть ключами, включая source и те, у которых нет исходящих рёбер. Если вершина D только принимает рёбра, но не отправляет — она всё равно должна присутствовать как adj['D'] = []. То же касается вершин, которые вообще не связаны с остальными. Это не прихоть: инициализация проходит по adj.keys(), и потерянная вершина не получит dist[v] = inf.

Рёбра ориентированные. Запись 'A': [('B', 3)] означает только путь A→B стоимостью 3. Если граф неориентированный, нужно добавить оба направления вручную. Все веса конечны и неотрицательны — это не техническое ограничение реализации, а условие корректности самого алгоритма.

Инициализация выглядит так:

dist = {v: float('inf') for v in adj}
dist[source] = 0
parent = {v: None for v in adj}

Здесь float('inf') — не просто удобная заглушка. Семантически dist[v] в любой момент работы алгоритма означает лучшую стоимость пути до v, найденную к данному моменту. Изначально мы не знаем ни одного пути ни до одной вершины, кроме источника, — отсюда бесконечность. Для источника путь из него в него самого стоит 0 по определению.

parent[v] = None для всех, включая source. При восстановлении источник служит явной точкой остановки; поэтому случай source == target сразу даёт путь из одной вершины.

По завершении алгоритма семантика dist[v] меняется: теперь это точная длина кратчайшего пути из source в v, либо inf, если v недостижима. Важно понимать это разграничение: во время работы значение ещё может улучшиться, после — нет.

Жадный выбор, релаксация рёбер и корректность для неотрицательных весов

Центральная идея Дейкстры — каждый раз извлекать из min-heap вершину с наименьшим известным расстоянием и считать это расстояние окончательным. Почему это работает?

Предположим от противного: мы извлекли вершину u с расстоянием d = dist[u], но существует более короткий путь P до u стоимостью d' < d. Путь P выходит из source и где-то пересекает границу между уже «зафиксированными» вершинами и ещё не обработанными. Возьмём на P первую незафиксированную вершину y и её непосредственного предшественника x, который уже зафиксирован.

Когда x обрабатывался, алгоритм выполнил релаксацию ребра x→y, поэтому dist[y] стало не больше стоимости префикса пути P от source до y. Обозначим эту стоимость cost(source→y). Поскольку все веса неотрицательны, оставшаяся часть пути от y до u не может иметь отрицательную длину, значит:

cost(source→y) ≤ cost(P) = d' < d

То есть dist[y] ≤ d' < d = dist[u]. Но тогда y должна была бы быть в куче с приоритетом меньше, чем у u, и извлечься раньше. Противоречие: u не могла бы оказаться минимумом.

Ключевое место — неравенство cost(source→y) ≤ cost(P). Оно выполняется только потому, что все веса неотрицательны. Именно здесь ломается логика при отрицательных рёбрах.

Представим граф: S→A стоимостью 2, S→B стоимостью 5, B→A стоимостью −10. После обработки S вершина A имеет минимальную текущую оценку 2 и извлекается раньше B. Но путь S→B→A стоит −5. Значит, первое актуальное извлечение A не фиксирует кратчайшее расстояние — ровно тот вывод, на котором держится Дейкстра.

Показанная ниже реализация не хранит множество settled, поэтому на этом конкретном графе она может позже снова положить A в кучу и в итоге получить −5. Это не восстанавливает общую гарантию Дейкстры: вершины могут обрабатываться повторно, оценка сложности исчезает, а при достижимом отрицательном цикле улучшения вообще не закончатся. Для графов с отрицательными рёбрами нужен алгоритм с другим доказательством корректности.

Релаксация ребра u→v с весом w — сама по себе простая операция:

new_d = d + w если new_d < dist[v]: обновить dist[v], parent[v], добавить (new_d, v) в кучу

Обновление строго при <: равный по стоимости путь не меняет dist[v] и не добавляет нового предшественника. Какой именно из равных кратчайших путей окажется в parent — зависит от порядка рёбер в списке смежности, и контракт этого не фиксирует.

Реализация через heapq: устаревшие записи и восстановление пути

Реализация должна безопасно разрешать равные приоритеты, пропускать устаревшие записи и сохранять предшественников для пути.

Тикет для безопасного сравнения. heapq в Python сравнивает элементы лексикографически. Если два элемента кучи имеют одинаковое расстояние, он попытается сравнить вершины — а вершины могут быть строками, числами или любыми другими hashable-объектами. Сравнение разных типов в Python 3 бросает TypeError. Решение: добавить монотонно растущий счётчик ticket в середину кортежа (distance, ticket, node). При равных distance сравниваются ticket, а до node дело не доходит никогда.

Устаревшие записи. Когда dist[v] улучшается, старая запись в куче не удаляется — heapq не поддерживает decrease-key. Вместо этого добавляется новая запись с меньшим расстоянием. Рано или поздно обе будут извлечены. Проверка if d != dist[u]: continue отсеивает старые: к моменту извлечения устаревшей записи dist[u] уже содержит лучшее значение.

import heapq

def dijkstra(adj, source):
    dist = {v: float('inf') for v in adj}
    dist[source] = 0
    parent = {v: None for v in adj}

    heap = []
    ticket = 0
    heapq.heappush(heap, (0, ticket, source))

    while heap:
        d, _, u = heapq.heappop(heap)
        if d != dist[u]:   # устаревшая запись — пропускаем
            continue
        for v, w in adj[u]:
            new_d = d + w
            if new_d < dist[v]:
                dist[v] = new_d
                parent[v] = u
                ticket += 1
                heapq.heappush(heap, (new_d, ticket, v))

    return dist, parent

Инвариант после heappop: если d == dist[u], то это первое актуальное извлечение u, и dist[u] уже окончательно. Все последующие записи для u в куче будут устаревшими и попадут под continue.

Восстановление пути. source и target должны быть ключами того же parent, который вернул запуск dijkstra(adj, source). Проходим по предшественникам от цели к источнику:

def reconstruct_path(parent, source, target):
    if parent[target] is None and target != source:
        return []   # target недостижима
    path = []
    cur = target
    while cur != source:
        path.append(cur)
        cur = parent[cur]
        if cur is None:
            return []   # parent получен не из запуска с этим source
    path.append(source)
    path.reverse()
    return path

Три граничных случая:

• Недостижимая вершина: dist[target] == float('inf'), parent[target] остался None. Условие target != source отделяет этот случай от следующего.
• source == target: цикл while cur != source не выполняется, после чего источник добавляется в путь; результат равен [source] и имеет стоимость 0.
• Несколько равных кратчайших путей: parent[v] хранит предшественника строгой релаксации, которая первой достигла итогового dist[v]; последующие равные кандидаты игнорируются. Функция вернёт один путь, зависящий от порядка обработки, но не обещает лексикографически минимальный вариант.

Проверим на маленьком примере:

adj = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
dist, parent = dijkstra(adj, 'A')
print(dist)   # {'A': 0, 'B': 1, 'C': 3, 'D': 4}
print(reconstruct_path(parent, 'A', 'D'))  # ['A', 'B', 'C', 'D']

Путь A→B→C→D стоит 1+2+1=4, и именно он в parent: сначала dist['C'] получило 4 через A→C, потом улучшилось до 3 через A→B→C, а затем dist['D'] улучшилось до 4 через A→B→C→D вместо прямого A→B→D стоимостью 6.

Сложность O((V+E) log V): условия и границы оценки

Разберём, откуда берётся привычная запись O((V+E) log V) и при каких условиях она честна.

Сколько операций с кучей? При неотрицательных весах каждое актуальное извлечение вершины происходит один раз, а её список исходящих рёбер сканируется один раз. Каждое рассмотренное ребро может породить не более одной успешной релаксации и одной новой записи. Вместе с начальной записью источника это O(E + 1) операций heappush и heappop; размер кучи также не превосходит O(E + 1). Одна операция стоит O(log(E + 2)): добавление 2 сохраняет константную стоимость и при E = 0. Обход ключей и списков смежности занимает O(V + E). Итоговая оценка:

T = O((V + E) log(E + 2))

Когда log(E+2) можно заменить на log V? Если граф простой — без параллельных рёбер между одной парой вершин, — то E ≤ V(V−1). Для V ≥ 2 отсюда log(E+2) = O(log V), и получается привычная запись O((V+E) log V).

Без условия простоты такая замена некорректна: в мультиграфе E может быть сколь угодно больше V², и безопасной остаётся оценка через log(E+2).

Разреженный vs. плотный граф. В разреженном графе E = O(V), и формула даёт O(V log V). В плотном E = O(V²), и O((V + V²) log V) = O(V² log V). Для плотных графов иногда выгоднее реализация с обычным массивом dist и линейным поиском минимума — она даёт O(V²) без логарифма. Но это уже другая реализация, не та, что мы разбирали.

Итого по памяти. Куча хранит до O(E + 1) записей, массивы dist и parent — по O(V) элементов. Суммарно O(V + E).

Для простого графа Дейкстра через heapq работает за O((V+E) log V). Если разрешены параллельные рёбра, безопасная общая оценка — O((V+E) log(E+2)).

Как продолжить практику

После этого разбора важно уметь выбирать между BFS и Дейкстрой по весам рёбер, восстанавливать путь и проверять несвязный граф. Для сравнения решений открыт соседний урок: BFS и восстановление пути. Текущий материал — бесплатное превью; полный курс алгоритмов и структур данных на Python платный. В его программе можно посмотреть последовательность тем и выбрать, подходит ли вам дальнейшая практика.