Кратчайшие пути: Дейкстра, Беллман–Форд, Флойд–Уоршелл, A*

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

При этом «алгоритмов кратчайшего пути» на самом деле не четыре и не десять. Есть одна операция — релаксация ребра — и есть разные дисциплины порядка, в котором эту операцию применяют. Дейкстра, Беллман–Форд, Флойд–Уоршелл, BFS, 0-1 BFS, A*, Джонсон — это всё разные ответы на вопрос «в каком порядке релаксировать рёбра, чтобы каждое пришлось трогать поменьше раз». Если держать это в голове, семейство перестаёт быть списком рецептов для заучивания и становится одной идеей с несколькими режимами.

Мы предполагаем, что вы уже свободно ориентируетесь в обходах графов (Обходы графов), понимаете язык асимптотики и инвариантов (Анализ алгоритмов) и знакомы с приоритетными очередями из курса Структуры данных.

1. Постановка и единственная операция, из которой всё растёт

Дан ориентированный граф G = (V, E) с весовой функцией w: E → ℝ. Вес пути — сумма весов его рёбер. Обозначим δ(u, v) — вес минимального по весу пути из u в v (+∞, если пути нет; −∞, если на каком-то пути в v достижим отрицательный цикл).

Различают три постановки:

Алгоритмы SSSP хранят массив оценок d[v] — текущую верхнюю границу на δ(s, v) — и массив предшественников parent[v] для восстановления пути. Вся работа сводится к одной операции:

def relax(u, v, w, d, parent):
    """Релаксация ребра (u, v): если через u дойти дешевле — обновляем оценку."""
    if d[u] + w < d[v]:
        d[v] = d[u] + w
        parent[v] = u
        return True          # оценка улучшилась
    return False

Название историческое и слегка сбивающее с толку: мы не «ослабляем», а натягиваем оценку вниз, к истинному расстоянию, как ослабляют натянутую резинку в физической модели.

Инвариант, общий для всех алгоритмов семейства. В любой момент выполнения d[v] ≥ δ(s, v), и d[v] равно весу какого-то реального пути из s в v (либо +∞). Доказывается индукцией по числу релаксаций: изначально d[s] = 0, остальные +∞; релаксация присваивает d[v] := d[u] + w(u,v), а это вес конкатенации пути, реализующего d[u], и ребра (u,v) — значит, не меньше δ(s,v).

Из инварианта следует главное: алгоритм не может ошибиться в меньшую сторону. Оценка никогда не опускается ниже правды. Значит, доказывать нужно ровно одно — что она в итоге до правды доходит. И вот тут алгоритмы расходятся.

Ключевая лемма о пути (path-relaxation property). Пусть s = v₀ → v₁ → … → v_k = v — кратчайший путь. Если рёбра этого пути были релаксированы в порядке (v₀,v₁), (v₁,v₂), …, (v_{k−1},v_k) — не обязательно подряд, между ними могло быть сколько угодно других релаксаций, — то после этого d[v] = δ(s, v) навсегда. Индукция по i: после релаксации (v_{i−1}, v_i) имеем d[v_i] ≤ d[v_{i−1}] + w = δ(s, v_{i−1}) + w = δ(s, v_i), а снизу оценка ограничена инвариантом.

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

2. Базовый случай: BFS и 0-1 BFS

Если все веса равны единице, порядок релаксаций задаётся бесплатно: обычная очередь. BFS обрабатывает вершины в порядке неубывания расстояния, поэтому когда вершина впервые попадает в очередь, её d уже окончательно. Это O(V + E) без всяких куч — и это идеальный образец того, к чему стремятся остальные алгоритмы.

Естественное обобщение — веса из {0, 1}. Здесь работает 0-1 BFS: вместо очереди берём дек, ребро веса 0 кладёт вершину в голову, ребро веса 1 — в хвост.

from collections import deque

def bfs01(graph, s, n):
    """graph[u] = список (v, w), где w ∈ {0, 1}. Время O(V + E), память O(V)."""
    INF = float('inf')
    d = [INF] * n
    d[s] = 0
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if d[u] + w < d[v]:
                d[v] = d[u] + w
                # вершины веса 0 обязаны обработаться раньше — кладём вперёд
                dq.appendleft(v) if w == 0 else dq.append(v)
    return d

Инвариант дека: в нём лежат вершины не более чем с двумя различными значениями d, причём меньшее — ближе к голове. Это ровно то же свойство монотонности, которое даёт корректность BFS, только с двумя «слоями» вместо одного. Аналогично для весов из небольшого целочисленного диапазона [0, C] работает алгоритм Диала — приоритетная очередь на массиве из C·V + 1 бакетов, O(E + C·V), без логарифма.

На практике 0-1 BFS постоянно всплывает там, где есть «бесплатные» и «платные» переходы: минимальное число разворотов на сетке дорог, минимальное число замен символов, минимальное число переключений слоёв в схеме.

3. Дейкстра

3.1 Интуиция

Представьте, что вы вылили в вершину s воду, и она растекается по рёбрам с единичной скоростью; вес ребра — его длина. Вершина «намокает» ровно в момент δ(s, v). Если пронаблюдать процесс, вершины намокают в порядке неубывания расстояния — и как только вершина намокла, её время уже не изменится: вода не течёт назад во времени.

Алгоритм Дейкстры — это дискретная симуляция этого процесса. Он поддерживает множество зафиксированных (settled) вершин, для которых d[v] = δ(s, v) уже доказано, и на каждом шаге берёт из оставшихся вершину с минимальной оценкой, объявляет её зафиксированной и релаксирует исходящие рёбра.

3.2 Доказательство корректности

Утверждение. В момент извлечения вершины u из очереди d[u] = δ(s, u).

Доказательство от противного. Пусть u — первая извлекаемая вершина, для которой d[u] > δ(s, u). Тогда u ≠ s, и существует кратчайший путь P: s ⇝ u веса δ(s,u) < ∞. Рассмотрим первое ребро (x, y) этого пути, где x уже зафиксирована, а y — ещё нет (такое существует: s зафиксирована, u — нет). По минимальности u для x верно d[x] = δ(s, x); при фиксации x ребро (x,y) было релаксировано, поэтому d[y] ≤ δ(s,x) + w(x,y) = δ(s,y), то есть d[y] = δ(s,y).

Так как y лежит на кратчайшем пути к u, а веса неотрицательны, участок y ⇝ u имеет неотрицательный вес, значит δ(s,y) ≤ δ(s,u). Получаем d[y] = δ(s,y) ≤ δ(s,u) < d[u]. Но u была извлечена как минимум по d в момент, когда y тоже лежала в очереди — противоречие. ∎

Обратите внимание, где именно использована неотрицательность: в шаге δ(s,y) ≤ δ(s,u). Это единственное место, и оно же — точка отказа.

На картинке видно, как это выглядит в жизни: вершина C фиксируется с оценкой 3 раньше, чем алгоритм добирается до B, а поздняя релаксация B → C веса −3 уже никого не интересует. Частая ошибка новичка — «Дейкстра всё равно работает, если отрицательное ребро одно» или «если отрицательных циклов нет». Нет, не работает: цикла в примере нет.

3.3 Реализация: ленивое удаление вместо decrease-key

Каноническая формулировка требует операции decrease-key. В heapq из стандартной библиотеки Python её нет, и в подавляющем большинстве продакшн-кода её сознательно не используют: вместо этого кладут в кучу дубликаты и отбрасывают устаревшие при извлечении.

import heapq

INF = float('inf')

def dijkstra(graph, s, n):
    """
    graph[u] = список (v, w), w >= 0.
    Ленивая куча: в куче до O(E) записей, устаревшие отбрасываются при извлечении.
    Время O((V + E) log E) = O((V + E) log V), память O(V + E).
    """
    d = [INF] * n
    parent = [-1] * n
    d[s] = 0
    pq = [(0, s)]                      # (оценка, вершина)
    while pq:
        du, u = heapq.heappop(pq)
        if du > d[u]:
            continue                   # устаревшая запись — вершина уже зафиксирована
        for v, w in graph[u]:
            nd = du + w
            if nd < d[v]:
                d[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return d, parent


def restore_path(parent, s, t):
    """Восстановление пути по массиву предшественников. O(длины пути)."""
    if parent[t] == -1 and t != s:
        return None                    # недостижима
    path = []
    while t != -1:
        path.append(t)
        t = parent[t]
    path.reverse()
    return path if path[0] == s else None

Три детали, которые отличают рабочий код от учебного:

1. if du > d[u]: continue — без этой строки алгоритм остаётся корректным, но релаксирует рёбра зафиксированных вершин повторно; на плотных графах это заметная потеря. Строка d[u] = du там не нужна: d[u] уже равно du.
2. Ранний выход. Если нужна одна пара s–t, добавьте if u == t: break после извлечения. На дорожной сети это экономит десятки процентов.
3. Кортежи против классов. В Python (nd, v) сравнивается лексикографически — при равных nd сравниваются номера вершин, что безопасно. Если вы кладёте в кучу объект, у которого нет __lt__, при коллизии по ключу вы получите TypeError в рантайме на редких входах. Классическая продовая мина.

3.4 Сложность и выбор структуры данных

Практический вывод, который расходится с учебниками: фибоначчиеву кучу почти никогда не используют. Её константа и промахи кэша съедают асимптотический выигрыш на любых реальных размерах; асимптотика O(E + V log V) выигрывает у бинарной кучи только на очень плотных графах, где всё равно лучше работает O(V²)-версия на массиве. На дорожных графах (E ≈ 2.5V) выигрывают 4-арные кучи и radix heaps — см. классический экспериментальный разбор Черкасского, Голдберга и Радзика, «Shortest paths algorithms: theory and experimental evaluation» (Mathematical Programming, 1996, https://link.springer.com/article/10.1007/BF02592101).

Теоретическая граница O(E + V log V) для сравнительной модели долго считалась непреодолимой — она упирается в «барьер сортировки»: Дейкстра выдаёт вершины отсортированными по расстоянию. В 2025 году Дуань, Мао, Мао, Шу и Инь показали детерминированный алгоритм за O(E log^{2/3} V), который барьер обходит, отказавшись от полного упорядочивания (https://arxiv.org/abs/2504.17033). Для практики это пока не имеет значения, но это первое за десятилетия структурное продвижение.

4. Беллман–Форд: когда веса могут быть отрицательными

4.1 Идея

Дейкстра требует знать, какую вершину фиксировать следующей. Беллман–Форд отказывается от этого знания и берёт грубой силой: релаксируем все рёбра V − 1 раз.

Почему V − 1 достаточно? Любой кратчайший путь (если отрицательных циклов нет) — простой, то есть содержит не более V − 1 ребра. После i-го полного прохода по всем рёбрам верно: d[v] = δ(s,v) для всех v, до которых существует кратчайший путь длиной не более i рёбер. Это прямое следствие леммы о релаксации пути: i-й проход обязательно включает релаксацию i-го ребра любого такого пути. После V − 1 проходов покрыты все простые пути.

Если на V-м проходе что-то ещё улучшилось — значит, существует путь из s длиной ≥ V рёбер, который короче любого простого. Это возможно только при отрицательном цикле, достижимом из s.

def bellman_ford(edges, n, s):
    """
    edges — список (u, v, w). Веса произвольные.
    Возвращает (d, parent, cycle) — cycle не None, если найден отрицательный цикл.
    Время O(V·E), память O(V).
    """
    d = [INF] * n
    parent = [-1] * n
    d[s] = 0
    x = -1                                   # вершина, «испорченная» на V-й итерации
    for i in range(n):
        x = -1
        for u, v, w in edges:
            if d[u] < INF and d[u] + w < d[v]:
                # -INF защищает от накопления «минус бесконечностей» на больших графах
                d[v] = max(d[u] + w, -INF)
                parent[v] = u
                x = v
        if x == -1:
            break                            # ничего не изменилось — можно выходить раньше
    if x == -1:
        return d, parent, None

    # Спускаемся по parent на n шагов, чтобы гарантированно попасть внутрь цикла
    y = x
    for _ in range(n):
        y = parent[y]
    cycle, cur = [], y
    while True:
        cycle.append(cur)
        cur = parent[cur]
        if cur == y:
            break
    cycle.reverse()
    return d, parent, cycle

Два места, где почти все ошибаются:

• if d[u] < INF. Без проверки INF + (−5) < INF — истина, и вы «улучшаете» расстояние до недостижимой вершины, ломая детекцию циклов.
• Возврат самого цикла. Простой ответ «цикл есть» бесполезен, если задача — найти валютный арбитраж или доказать неразрешимость системы ограничений. Спуск по parent на n шагов — стандартный приём: он гарантированно приводит внутрь цикла, даже если x лежит не на нём, а лишь достижима из него.

4.2 Ранний выход, SPFA и реальные вероятности

Практическая версия почти никогда не делает V − 1 проход: она останавливается, как только проход ничего не изменил. Отсюда популярная оптимизация — SPFA (Shortest Path Faster Algorithm, он же Беллман–Форд в очереди): держим очередь «вершин, чья оценка изменилась», и релаксируем только исходящие из них рёбра. На случайных графах SPFA ведёт себя как O(E), но худший случай остаётся O(VE), и на специально построенных антитестах (сетки с определённой структурой весов) он именно туда и падает. На олимпиадах это регулярно приводит к TLE, в проде — к тому, что «быстрый алгоритм» внезапно перестаёт укладываться в SLA на конкретном клиенте.

4.3 Зачем это нужно: системы разностных ограничений

Самое красивое применение Беллмана–Форда — не поиск путей, а решение систем неравенств вида x_j − x_i ≤ c. Каждое такое ограничение превращается в ребро i → j веса c; добавляем фиктивный источник s с рёбрами веса 0 во все вершины и запускаем Беллман–Форд.

• Система разрешима ⟺ нет отрицательного цикла.
• Тогда x_i = d[s, i] — корректное решение (по неравенству треугольника d[j] ≤ d[i] + c, что и есть x_j − x_i ≤ c).

Это буквально движок расписаний: «задача B стартует не раньше чем через 3 дня после A», «разница между двумя часами в распределённой системе не превышает ε». В компиляторах на этом стоят проверки временны́х ограничений в RTL-синтезе, в верификации — difference bound matrices для timed automata. Разбор в CLRS, глава 24.4.

Второе применение — валютный арбитраж. Возьмём логарифм: путь минимального веса по рёбрам −log(курс) соответствует произведению максимального курса, а отрицательный цикл — цепочке обменов, возвращающей больше, чем вложено.

5. Флойд–Уоршелл и алгебра кратчайших путей

5.1 Динамика по «разрешённым промежуточным вершинам»

Пусть D_k[i][j] — вес кратчайшего пути из i в j, которому разрешено проходить через промежуточные вершины только из {1, …, k}. Тогда

D_k[i][j] = min( D_{k−1}[i][j],  D_{k−1}[i][k] + D_{k−1}[k][j] )

Либо вершину k не используем, либо путь проходит через k ровно один раз (дважды не имеет смысла — цикл только ухудшит вес, если нет отрицательных циклов). Ответ — D_n.

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

def floyd_warshall(n, w):
    """
    w[i][j] — вес ребра (INF если ребра нет), w[i][i] = 0.
    Время O(V³), память O(V²). Работает с отрицательными рёбрами.
    Возвращает (dist, nxt); nxt — для восстановления пути.
    """
    dist = [row[:] for row in w]
    nxt = [[j if w[i][j] < INF else -1 for j in range(n)] for i in range(n)]

    for k in range(n):                    # ВНЕШНИЙ цикл — только по k
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue                  # микрооптимизация: строка i через k не улучшится
            di = dist[i]
            for j in range(n):
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd
                    nxt[i][j] = nxt[i][k]

    # Отрицательный цикл ⟺ dist[i][i] < 0 для какой-то вершины i
    negative = [i for i in range(n) if dist[i][i] < 0]
    return dist, nxt, negative


def fw_path(nxt, i, j):
    """Восстановление пути: O(длины пути)."""
    if nxt[i][j] == -1:
        return None
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path

Про память: dist перезаписывается на месте, без хранения всех n слоёв. Это законно, хотя и требует аккуратного доказательства: dist[i][k] и dist[k][j] на итерации k уже не изменятся, потому что D_k[i][k] = D_{k−1}[i][k] (путь в k не выигрывает от прохода через k).

Флойд–Уоршелл — это O(V³) времени и O(V²) памяти. Память здесь часто оказывается жёстче времени: на V = 20 000 матрица из 4-байтовых чисел — это 1.6 ГБ. Практический предел — примерно V ≤ 5 000.

5.2 Тот же цикл — три разных алгоритма

Красота формулировки в том, что она параметризуется полукольцом. Замените (min, +) на другую пару операций — и получите другой алгоритм с той же тройной петлёй:

Умножение матриц в (min, +) называют дистанционным произведением. Отсюда же следует, что «кратчайший путь ровно из k рёбер» решается быстрым возведением в степень: O(V³ log k). На этом же наблюдении стоят субкубические алгоритмы APSP вроде O(V³ / 2^{Ω(√log V)}) Уильямса (https://arxiv.org/abs/1312.6680) — практического значения не имеют, теоретическое велико.

5.3 Джонсон: потенциалы и переваживание

Флойд–Уоршелл — O(V³). На разреженном графе (E ≈ V) это расточительно: V запусков Дейкстры дали бы O(VE log V) ≈ O(V² log V). Мешают только отрицательные рёбра.

Алгоритм Джонсона их убирает. Введём потенциал φ: V → ℝ и определим переваженную функцию

w'(u, v) = w(u, v) + φ(u) − φ(v)

Ключевое свойство: вес любого пути u ⇝ v меняется на φ(u) − φ(v) — константу, зависящую только от концов. Промежуточные потенциалы телескопируются и сокращаются. Значит, множество кратчайших путей между любой парой не меняется. А для циклов φ(u) − φ(u) = 0 — вес цикла инвариантен, поэтому переваживание не может ни создать, ни уничтожить отрицательный цикл.

Осталось выбрать φ так, чтобы все w' стали неотрицательными. Возьмём фиктивную вершину q с рёбрами веса 0 во все вершины и положим φ(v) = δ(q, v), посчитав его Беллманом–Фордом. Неравенство треугольника δ(q,v) ≤ δ(q,u) + w(u,v) — это ровно w(u,v) + φ(u) − φ(v) ≥ 0. Готово.

def johnson(n, edges, adj):
    """
    APSP на разреженном графе с отрицательными рёбрами.
    Время O(V·E + V·(V+E)·log V), память O(V + E) сверх выхода.
    """
    # 1. Фиктивный источник q = n с нулевыми рёбрами во все вершины
    ext = edges + [(n, v, 0) for v in range(n)]
    phi, _, cycle = bellman_ford(ext, n + 1, n)
    if cycle is not None:
        raise ValueError("отрицательный цикл — APSP не определён")

    # 2. Переваживание: w'(u,v) = w(u,v) + phi[u] - phi[v] >= 0
    adj2 = [[(v, w + phi[u] - phi[v]) for v, w in adj[u]] for u in range(n)]

    # 3. Дейкстра из каждой вершины и обратный пересчёт
    result = []
    for u in range(n):
        d2, _ = dijkstra(adj2, u, n)
        result.append([d2[v] - phi[u] + phi[v] if d2[v] < INF else INF
                       for v in range(n)])
    return result

Идея потенциалов — не частный трюк Джонсона. Это тот же математический объект, что двойственные переменные в линейном программировании, что «стоимость до цели» в reduced cost в min-cost flow (см. Остовные деревья и потоки) и — как мы сейчас увидим — что эвристика в A*.

6. A*: Дейкстра, которому подсказали направление

6.1 От потенциалов к эвристике

Дейкстра растекается во все стороны одинаково. Но если мы ищем путь из Москвы в Казань по дорожной сети, раскрывать вершины в сторону Смоленска бессмысленно — они заведомо дальше от цели. Формализуем это: пусть h(v) — оценка снизу оставшегося расстояния δ(v, t). Возьмём φ(v) = −h(v) в качестве потенциала и переваженим граф:

w'(u, v) = w(u, v) − h(u) + h(v)

Запустим на переваженном графе обычную Дейкстру. Так как приоритет вершины при этом становится g(v) − h(s) + h(v), а h(s) — константа, порядок извлечения задаётся величиной

f(v) = g(v) + h(v)

Это и есть A*. Он не «другой алгоритм» — это в точности Дейкстра на графе, переваженном эвристикой. Отсюда мгновенно следуют оба условия корректности:

• Допустимость (admissible): h(v) ≤ δ(v, t) для всех v, и h(t) = 0. Нужна, чтобы A* не отбросил оптимальный путь и вернул правильный ответ (в древовидном поиске без повторного открытия).
• Согласованность / монотонность (consistent): h(u) ≤ w(u,v) + h(v) для каждого ребра. Это дословно w'(u,v) ≥ 0 — условие применимости Дейкстры. При согласованной h вершина, извлечённая из очереди, зафиксирована окончательно, и переоткрывать её не нужно. Согласованность влечёт допустимость (индукция вдоль пути к t).

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

Два крайних случая проясняют картину. При h ≡ 0 A* вырождается в Дейкстру. При h(v) = δ(v, t) (идеальная эвристика) все рёбра на кратчайшем пути получают w' = 0, и алгоритм идёт прямо по нему, не раскрывая ничего лишнего. Всё интересное — между.

6.2 Реализация

import heapq

def astar(neighbors, s, t, h):
    """
    neighbors(u) -> итератор (v, w); h(v) -> допустимая и согласованная оценка до t.
    Работает на неявном графе (сетка, состояния головоломки) — без материализации V.
    Время в худшем случае как у Дейкстры; на практике определяется качеством h.
    """
    g = {s: 0}
    parent = {s: None}
    closed = set()
    pq = [(h(s), 0, s)]                    # (f, g, вершина)

    while pq:
        _, gu, u = heapq.heappop(pq)
        if u == t:
            return gu, _restore(parent, t)
        if u in closed:
            continue                       # устаревшая запись
        closed.add(u)
        for v, w in neighbors(u):
            ng = gu + w
            if ng < g.get(v, INF):
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h(v), ng, v))
    return INF, None


def _restore(parent, t):
    path = []
    while t is not None:
        path.append(t)
        t = parent[t]
    return path[::-1]

Тонкость: if u == t: return после извлечения из кучи, а не в момент релаксации. Проверка при релаксации даёт первый найденный путь, а не кратчайший — классический баг, который на сетках 4-связности с манхэттенской эвристикой почти не проявляется и вылезает на графах с разными весами.

6.3 Откуда брать эвристику

Отдельно про ALT (A*, Landmarks, Triangle inequality, Goldberg & Harrelson, 2005, https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/): предвычисляем расстояния от небольшого набора «маяков» до всех вершин; по неравенству треугольника |δ(L,t) − δ(L,v)| ≤ δ(v,t), что даёт допустимую эвристику без всякой геометрии. Работает на графах, где координат нет вовсе.

Ошибка масштаба, которая стоила многим часов отладки: если веса рёбер — это время в секундах, а h — расстояние в метрах, эвристика чудовищно завышена, допустимость нарушена, и A* уверенно возвращает не кратчайший путь. Единицы измерения g и h обязаны совпадать, и h обязана делиться на максимально возможную скорость, а не на среднюю.

6.4 Варианты A*

• Weighted A*: f = g + ε·h, ε > 1. Теряет оптимальность, но даёт гарантию ε-приближения и на порядок быстрее. В робототехнике и играх — стандарт.
• IDA* — итеративное углубление по порогу f. Память O(глубины) вместо O(V). Именно так Корф впервые решил 15-puzzle оптимально.
• D* Lite — инкрементальный перепланировщик для меняющейся карты; пересчитывает только затронутую часть. Используется в наземных роверах NASA и в ROS (http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf).
• Двунаправленный A* — корректная остановка здесь нетривиальна и требует согласованных потенциалов с обеих сторон; наивное «встретились — стоп» даёт неоптимальный ответ.

7. Что делают в проде

Реальные системы почти никогда не запускают чистого Дейкстру на полном графе.

Дорожная маршрутизация. Граф Европы — порядка 20 млн вершин и 50 млн рёбер. Дейкстра отработает за секунды — недопустимо для интерактивной карты. Поэтому все современные движки (OSRM, GraphHopper, Valhalla, движки Google и Яндекса) используют предвычисление. Два основных подхода:

• Contraction Hierarchies (Geisberger et al., 2008): вершины упорядочиваются по «важности» и последовательно стягиваются с добавлением shortcut-рёбер. Запрос — двунаправленный Дейкстра, идущий только «вверх» по иерархии. Ускорение в тысячи раз, ответ точный. Обзор: «Route Planning in Transportation Networks» (https://arxiv.org/abs/1504.05140) — лучший единый источник по теме.
• Hub Labeling / CRP — предвычисленные метки, дающие запрос за микросекунды, ценой десятков гигабайт. CRP (Customizable Route Planning) в Bing Maps умеет перестраивать метрику под пробки за секунды, не трогая топологию.

Сетевая маршрутизация. OSPF и IS-IS — это буквально Дейкстра: каждый роутер получает полную карту сети (link-state database) и считает SPF-дерево локально. RIP — это распределённый Беллман–Форд, и его знаменитая болезнь count-to-infinity — прямое следствие того, что вершина не знает, проходит ли чужая оценка через неё саму.

Именно из-за этого дефекта распределённого Беллмана–Форда крупные сети перешли на link-state протоколы, а BGP использует path-vector — он передаёт не только стоимость, но и весь AS-путь, что позволяет обнаружить петлю напрямую.

Другие места. Диспетчеризация в ride-hailing (many-to-many запросы поверх CH), роутинг в играх (weighted A* + иерархические сетки), выбор пути свопов в DeFi-агрегаторах (Беллман–Форд по логарифмам курсов), планирование движений манипулятора в конфигурационном пространстве, seam carving в обработке изображений (кратчайший путь в DAG), выравнивание последовательностей в биоинформатике.

8. Типичные ошибки — чеклист

1. Дейкстра на отрицательных рёбрах. Работает на ваших тестах, врёт на проде. Есть отрицательные веса — Беллман–Форд, Джонсон или (если граф ациклический) топологический порядок.
2. INF + w без проверки достижимости. Переполнение при INF = 2^31 − 1 в C++/Java даёт отрицательное число и «улучшает» расстояние до недостижимой вершины. Берите INF = 4·10^18 для int64 или проверяйте d[u] < INF явно.
3. Цикл по k не снаружи во Флойде–Уоршелле.
4. Проверка u == t при релаксации, а не при извлечении в Дейкстре и A*.
5. Забытый if du > d[u]: continue при ленивой куче — асимптотика формально та же, константа хуже в разы.
6. Недопустимая эвристика в A*: не те единицы измерения, деление на среднюю скорость вместо максимальной, эвристика «по прямой» при наличии более быстрых рёбер, чем предполагает метрика.
7. decrease-key на куче без индексов вершин. Попытка «обновить элемент в heapq» через удаление по значению — O(V) и гонки в многопоточном коде.
8. Восстановление пути через повторный поиск. Массив parent стоит O(V) памяти и даёт путь за O(длины); отдельный проход — лишняя работа и источник расхождений при равных по весу путях.
9. Отрицательный цикл, недостижимый из s. Беллман–Форд из s его не увидит. Если нужна проверка «есть ли отрицательный цикл где угодно» — инициализируйте все d[v] = 0 (эквивалент фиктивного источника) или используйте Флойда–Уоршелла.
10. Смешение «кратчайший по числу рёбер» и «кратчайший по весу». На графе с весами BFS даёт первый, а не второй, — и это самый молчаливый из всех багов.

9. Итоговая таблица

Мини-итог. Всё семейство — это одна релаксация плюс дисциплина порядка. Неотрицательные веса дают монотонность и позволяют фиксировать вершины по одной (Дейкстра). Отрицательные веса монотонность убивают, и приходится платить полными проходами (Беллман–Форд) или сначала чинить веса потенциалами (Джонсон). Знание о цели превращается в потенциал и сужает область поиска (A*). Потребность во всех парах меняет саму формулировку ДП (Флойд–Уоршелл). Если вы понимаете, какое из этих четырёх обстоятельств у вас в задаче, алгоритм выбирается однозначно.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд., главы 22–23 (SSSP, APSP, разностные ограничения) — https://mitpress.mit.edu/9780262046305/
• Sedgewick, Wayne. Algorithms, 4-е изд., глава 4.4 — https://algs4.cs.princeton.edu/44sp/
• Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959 — https://link.springer.com/article/10.1007/BF01386390 (оригинал, две страницы, читается легко)
• Hart, Nilsson, Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths, 1968 — https://ieeexplore.ieee.org/document/4082128
• Bast et al. Route Planning in Transportation Networks, 2015 — https://arxiv.org/abs/1504.05140
• Cherkassky, Goldberg, Radzik. Shortest paths algorithms: theory and experimental evaluation, 1996 — https://link.springer.com/article/10.1007/BF02592101
• Duan, Mao, Mao, Shu, Yin. Breaking the Sorting Barrier for Directed SSSP, 2025 — https://arxiv.org/abs/2504.17033
• Red Blob Games — интерактивные визуализации A* и эвристик — https://www.redblobgames.com/pathfinding/a-star/introduction.html
• Competitive Programming Algorithms (cp-algorithms) — компактные эталонные реализации — https://cp-algorithms.com/graph/dijkstra.html

Что дальше

Кратчайшие пути отвечают на вопрос «как дешевле всего добраться». Следующий шаг — задачи, где нужно связать весь граф минимальной ценой или пропустить через него максимальный поток: там появляются другой набор жадных аргументов, теорема о максимальном потоке и минимальном разрезе и красивая двойственность, в которой потенциалы из этой статьи всплывут снова уже как reduced cost.

Остовные деревья и потоки в сетях