Алгоритм Дейкстры: жадность, которая оказывается точной

Если ты помнишь алгоритм, умеешь доказать, почему извлечённая вершина уже окончательна, и знаешь три реализации с их ценой, листай до «Теперь сам».

Как думаешь, когда оценку можно считать окончательной

Мы держим оценки сверху dist и улучшаем их релаксациями. Прежде чем читать дальше, ответь: в какой момент про вершину можно сказать «всё, дешевле уже не будет» и больше её не трогать? И чем для этого ответа важно, что все веса неотрицательны?

На что это похоже

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

Механизм: очередь с приоритетами и ленивое удаление

import heapq                                # стандартная куча Python

def dijkstra(start):
    dist = [INF] * V                       # INF - заведомо большое число (см. прошлый урок)
    prev = [-1] * V                        # откуда пришли; -1 значит «неизвестно»
    dist[start] = 0
    q = [(0, start)]                       # (оценка, вершина) - min-куча
    while q:
        d, v = heapq.heappop(q)
        if d > dist[v]:
            continue                       # устаревшая запись - пропускаем
        for u, w in adj[v]:                # сосед и вес ребра
            if dist[v] + w < dist[u]:
                dist[u] = dist[v] + w
                prev[u] = v
                heapq.heappush(q, (dist[u], u))   # новая запись, старая станет мусором
    return dist, prev

Про листинг: это обычный Python, heapq и V/adj - куча из стандартной библиотеки и данные графа (число вершин и список смежности), которые заводятся снаружи функции. В ЗАДАЧАХ курса импортов нет и кучи тоже: там вершину с наименьшей оценкой находят перебором массива - это третья строка таблицы ниже, O(V²), и на графах из условий она быстрее.

Это ЛЕНИВЫЙ вариант из главы про очередь с приоритетами: вместо того чтобы искать вершину в куче и менять её ключ, мы кладём новую запись, а устаревшие отбрасываем при извлечении по проверке d > dist[v]. Записей в куче становится до E, но код остаётся коротким, и на практике так и пишут.

Три реализации и их цена:

двоичная куча, ленивая   : O((V + E)·log V)   ← обычный выбор
куча Фибоначчи с
  уменьшением ключа      : O(E + V·log V)     ← лучшая ОЦЕНКА из трёх
массив без кучи
  (каждый раз ищем min)  : O(V² + E) = O(V²)  ← простой выбор при E ≈ V²

Читать эту таблицу надо так. На разреженном графе (E ≈ V) двоичная куча выигрывает у перебора массива: V·log V против V². На плотном (E ≈ V²) - наоборот: перебор даёт V², а куча V²·log V. Куча Фибоначчи лучше ДВОИЧНОЙ кучи на любом графе (E + V·log V никогда не хуже (V + E)·log V), а на плотном графе она даёт те же V², что и перебор массива. Но множитель у неё большой, а код длинный, поэтому на практике берут либо двоичную кучу, либо, на плотном графе, перебор массива - он и короче, и без единой лишней структуры.

Правило

Дейкстра: держим оценки dist, повторно берём НЕОБРАБОТАННУЮ вершину с наименьшей оценкой, объявляем её окончательной и релаксируем её рёбра. Требует НЕОТРИЦАТЕЛЬНЫХ весов. Цена - O((V + E)·log V) на двоичной куче с ленивым удалением, O(E + V·log V) с уменьшением ключа, O(V²) перебором массива на плотном графе. Маршрут восстанавливается по prev.

Разбор: считаем по шагам

Граф (ориентированный): s→a = 4, s→b = 1, b→a = 2, a→t = 1, b→t = 7.

старт: dist = {s:0, a:∞, b:∞, t:∞},  куча [(0,s)]

извлекаем (0, s)  → фиксируем s = 0
    релаксируем s→a: dist[a] = 4, кладём (4,a)
    релаксируем s→b: dist[b] = 1, кладём (1,b)
извлекаем (1, b)  → фиксируем b = 1      ← минимум, а не «кто раньше пришёл»
    релаксируем b→a: 1 + 2 = 3 < 4 → dist[a] = 3, кладём (3,a)
    релаксируем b→t: 1 + 7 = 8 < ∞ → dist[t] = 8, кладём (8,t)
извлекаем (3, a)  → фиксируем a = 3
    релаксируем a→t: 3 + 1 = 4 < 8 → dist[t] = 4, кладём (4,t)
извлекаем (4, t)  → фиксируем t = 4      ← ключ тот же, что у (4,a): кучу выбор не волнует
извлекаем (4, a)  → d=4 > dist[a]=3 → УСТАРЕВШАЯ запись, пропускаем
извлекаем (8, t)  → d=8 > dist[t]=4 → устаревшая, пропускаем

Ответ: dist = {s:0, b:1, a:3, t:4}, маршрут s → b → a → t. Обрати внимание на три вещи. Первая: вершины фиксировались в порядке 0, 1, 3, 4 - по возрастанию расстояния, а не по порядку появления. Вторая: в куче осталось два мусорных элемента, и они были отброшены проверкой одной строкой - именно так работает ленивое удаление. Третья: записи (4, t) и (4, a) имеют ОДИНАКОВЫЙ ключ, и какую из них куча выдаст первой - её внутреннее дело (Python сравнит вторые элементы пары и выдаст (4, a), другая реализация может выдать (4, t)). На ответ это не влияет: a уже зафиксирована с оценкой 3, её запись всё равно будет отброшена как устаревшая. Правило простое: там, где ключи равны, порядок фиксации не определён, и алгоритм не должен от него зависеть.

Разбор: почему извлечённая вершина уже окончательна

Это главное утверждение алгоритма, и доказательство короткое. Пусть все веса неотрицательны, и пусть мы извлекаем из кучи вершину u с наименьшей оценкой среди необработанных. Докажем, что dist[u] уже равно истинному кратчайшему расстоянию.

От противного: пусть есть путь из s в u короче, чем dist[u]. Идём по этому пути от начала. Стартовая вершина обработана, u - нет, значит где-то на пути есть первое ребро x → y, где x уже обработана, а y ещё нет. Когда мы обрабатывали x, мы релаксировали это ребро, значит dist[y] <= dist[x] + w(x, y), а это - длина куска пути от s до y.

Дальше решает НЕОТРИЦАТЕЛЬНОСТЬ весов: оставшийся кусок пути от y до u имеет длину >= 0, поэтому длина всего пути >= dist[y]. Мы предположили, что весь путь короче dist[u], значит dist[y] < dist[u]. Но y не обработана, а u мы выбрали как необработанную вершину с НАИМЕНЬШЕЙ оценкой - противоречие.

Вот и вся доказательная работа. И сразу видно, где она сломается: если бы существовали отрицательные рёбра, «оставшийся кусок пути >= 0» перестало бы выполняться, и вершина с маленькой оценкой могла бы подешеветь ПОСЛЕ фиксации. Контрпример на три вершины будет в следующем уроке.

Что ломается без этого

Первое: брать вершину «по порядку очереди», а не по минимуму - получится обход в ширину, который на весах врёт. Второе: забыть проверку if d > dist[v]: continue в ленивом варианте - вершина будет обрабатываться по нескольку раз, и хотя ответ обычно останется верным, время вырастет, а на плохих графах заметно. Третье: класть в кучу вершину без её оценки (heappush(q, v)) - куча начнёт сравнивать номера вершин вместо расстояний, и алгоритм превратится в мусор. Четвёртое: применять Дейкстру к отрицательным весам «потому что обычно работает» - именно так и появляются баги, которые всплывают на редких данных. Пятое: на плотном графе тащить кучу, когда перебор массива и проще, и быстрее.

Зачем это в работе

Дейкстра - рабочая лошадь навигации и маршрутизации: маршруты в картах (с весом «время с учётом пробок»), протоколы состояния канала в сетях (каждый маршрутизатор знает всю карту сети - вершины это маршрутизаторы, рёбра это каналы с «метрикой» вместо длины - и считает по ней кратчайшие пути; так работают OSPF и IS-IS), планирование перемещений роботов и юнитов в играх, поиск самой дешёвой цепочки преобразований - от конвертации валют до подбора последовательности операций. На огромных дорожных графах его дополняют предобработкой (иерархии сокращений, contraction hierarchies) и двунаправленным поиском, но ядро остаётся тем же. И отдельный практический вывод: если веса одинаковые, не зови Дейкстру - обход в ширину даст тот же ответ и без кучи; если веса маленькие целые (0 и 1), существует отдельный дешёвый трюк - дека вместо кучи, об этом в конце главы.

Теперь сам

Граф: s→a = 2, s→b = 5, a→b = 1, a→c = 7, b→c = 1, c→t = 2, b→t = 9. Проведи Дейкстру из s и выпиши, в каком порядке фиксируются вершины и каким получится dist[t].