Кратчайшие пути: Дейкстра и 0-1 BFS

Когда у дорог разная длина, BFS уже не годится. Дейкстра на куче и 0-1 BFS на деке находят кратчайшие пути во взвешенном графе.

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными весами рёбер за O((n + m) log n) с использованием кучи.

Зачем это нужно

BFS находит кратчайший путь, только если все рёбра «весят» одинаково. Но дороги бывают разной длины, переходы — разной стоимости. Здесь нужен алгоритм, учитывающий веса. Дейкстра — золотой стандарт для графов с неотрицательными весами и одна из самых частых тем на олимпиадах уровня USACO Gold и Codeforces. А для частного случая, когда веса рёбер — только 0 и 1, есть изящный и более быстрый приём — 0-1 BFS.

Идея Дейкстры «на пальцах»

Дейкстра — это «жадный BFS с приоритетами». Мы поддерживаем оценку кратчайшего расстояния dist[v] до каждой вершины. На каждом шаге берём ещё не финализированную вершину с наименьшим dist (её расстояние уже точно минимально — доказывается тем, что веса неотрицательны) и «расслабляем» её рёбра: если через неё до соседа короче, обновляем оценку соседа. Чтобы быстро находить вершину с минимальным dist, используем кучу (приоритетную очередь) из раздела 3.

Реализация Дейкстры на куче

import heapq

n = 5
# граф: вершина -> список (вес, куда)
g = {0: [(2, 1), (5, 2)], 1: [(1, 2), (2, 3)], 2: [(2, 4)],
     3: [(1, 4)], 4: []}

def dijkstra(src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]                 # куча пар (расстояние, вершина)
    while pq:
        d, u = heapq.heappop(pq)    # вершина с наименьшим расстоянием
        if d > dist[u]:
            continue                # устаревшая запись — пропускаем
        for w, v in g[u]:
            if d + w < dist[v]:     # нашли путь короче — расслабляем
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

print("Кратчайшие пути от 0:", dijkstra(0))

Два ключевых момента. Первый — пары (расстояние, вершина) в куче: она автоматически отдаёт вершину с минимальным расстоянием. Второй — проверка if d > dist[u]: continue: это ленивое удаление. Куча не умеет менять приоритет, поэтому мы просто кладём новую запись, а устаревшие (с большим d) пропускаем при извлечении. Проверим путь до вершины 4: 0→1→3→4 даёт 2+2+1 = 5, что меньше 0→1→2→4 = 2+1+2 = 5 (одинаково) и 0→2→4 = 5+2 = 7 — итог 5.

Вывод:

Кратчайшие пути от 0: [0, 2, 3, 4, 5]

Восстановление самого пути

Часто нужна не только длина кратчайшего пути, но и сам маршрут. Для этого заводим массив parent[v] — из какой вершины мы пришли в v на кратчайшем пути. При каждом успешном «расслаблении» записываем parent[v] = u, а в конце разворачиваем цепочку от цели к источнику.

import heapq

n = 5
g = {0: [(2, 1), (5, 2)], 1: [(1, 2), (2, 3)], 2: [(2, 4)],
     3: [(1, 4)], 4: []}

def dijkstra_path(src, dst):
    INF = float("inf")
    dist = [INF] * n
    parent = [-1] * n          # откуда пришли в вершину
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for w, v in g[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u          # запоминаем предшественника
                heapq.heappush(pq, (dist[v], v))
    # разворачиваем путь от dst к src
    path = []
    cur = dst
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    return dist[dst], path

length, path = dijkstra_path(0, 4)
print("Длина:", length, "| Путь:", path)

Приём тот же, что при восстановлении ответа в ДП: храним «откуда пришли» и в конце идём по цепочке назад. Найденный путь 0 → 1 → 2 → 4 имеет длину 2+1+2 = 5 (кратчайших путей здесь несколько одинаковой длины, алгоритм вернул один из них). Эта техника универсальна — она работает и для BFS, и для любого алгоритма, где есть понятие «предшественника на оптимальном пути».

Вывод:

Длина: 5 | Путь: [0, 1, 2, 4]

0-1 BFS: когда веса только 0 и 1

Если все веса — это 0 или 1 (типично: «бесплатный» переход против «платного»), Дейкстру можно заменить на более быстрый 0-1 BFS на деке. Идея: ребро веса 0 не увеличивает расстояние, поэтому сосед должен обрабатываться раньше — кладём его в начало дека (appendleft); ребро веса 1 — в конец (append). Так дек всегда хранит вершины в порядке неубывания расстояния, и не нужна куча.

from collections import deque

n = 4
# рёбра с весами 0/1: вершина -> [(вес, куда)]
g = {0: [(0, 1), (1, 2)], 1: [(1, 3)], 2: [(0, 3)], 3: []}

def bfs01(src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for w, v in g[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)   # вес 0 — в начало
                else:
                    dq.append(v)       # вес 1 — в конец
    return dist

print("0-1 BFS расстояния от 0:", bfs01(0))

Сложность 0-1 BFS — O(n + m), то есть быстрее Дейкстры (нет логарифма от кучи). Проверим вершину 3: путь 0→1(0)→3(1) = 1, а 0→2(1)→3(0) = 1 — оба дают 1.

Вывод:

0-1 BFS расстояния от 0: [0, 0, 1, 1]

Какой алгоритм когда

Подводные камни

• Дейкстра не работает с отрицательными весами. Это её главное ограничение; при отрицательных рёбрах нужен Беллман-Форд.
• Ленивое удаление обязательно. Без проверки if d > dist[u]: continue алгоритм всё равно корректен, но обрабатывает лишние записи; на больших графах это важно для скорости.
• Восстановление пути. Чтобы вывести сам путь (а не только длину), храни массив parent[v] — предшественника на кратчайшем пути.
• 0-1 BFS требует именно весов 0/1; для произвольных малых весов есть обобщения, но базовый приём — только для двоичных.

Итог

• Дейкстра находит кратчайшие пути при неотрицательных весах за O((n+m) log n) с помощью кучи пар (dist, вершина).
• Ленивое удаление: устаревшие записи в куче пропускают по условию d > dist[u].
• При весах 0/1 быстрее 0-1 BFS на деке: вес 0 — в начало, вес 1 — в конец, итог O(n+m).
• Отрицательные веса — не для Дейкстры; там Беллман-Форд.