0-1 BFS: кратчайший путь за O(V+E) без Дейкстры

Коротко

Если веса ограничены нулём и единицей, логарифм из Дейкстры исчезает — достаточно дека вместо приоритетной очереди.

Идея

Обычный BFS работает, потому что вершины извлекаются в порядке возрастания расстояния. С весами 0 и 1 это свойство можно сохранить одним приёмом.

При переходе по ребру:

• вес 0 — расстояние не изменилось, вершину кладём в начало дека;
• вес 1 — расстояние выросло на единицу, кладём в конец.

Дек остаётся упорядоченным по расстоянию, причём разница между первым и последним элементом никогда не превышает единицы. Это и заменяет приоритетную очередь.

дек:  [ d ][ d ][ d ][ d+1 ][ d+1 ]
        ↑                        ↑
   сюда кладём вес 0        сюда вес 1

Реализация

from collections import deque


def zero_one_bfs(graph: dict, start, n: int) -> dict:
    """graph: вершина -> список (сосед, вес 0 или 1)."""
    INF = float('inf')
    dist = {v: INF for v in graph}
    dist[start] = 0

    dq = deque([start])

    while dq:
        v = dq.popleft()

        for to, weight in graph[v]:
            if dist[v] + weight < dist[to]:
                dist[to] = dist[v] + weight

                if weight == 0:
                    dq.appendleft(to)     # то же расстояние — вперёд очереди
                else:
                    dq.append(to)         # расстояние больше — в конец

    return dist


graph = {
    'a': [('b', 0), ('c', 1)],
    'b': [('d', 1)],
    'c': [('d', 0)],
    'd': [],
}

print(zero_one_bfs(graph, 'a', 4))
# {'a': 0, 'b': 0, 'c': 1, 'd': 1}

Вершина может попасть в дек несколько раз — это нормально. Проверка dist[v] + weight < dist[to] отсекает устаревшие записи, как и в Дейкстре с ленивым удалением.

Классическая задача: минимум разворотов

Дана сетка со стрелками направлений. Разрешено идти по стрелке бесплатно или развернуть её ценой одной операции. Найти минимальное число разворотов, чтобы добраться из точки А в Б.

Естественная модель: ребро по направлению стрелки имеет вес 0, против — вес 1. Ровно случай для 0-1 BFS.

from collections import deque


def min_flips(grid: list[str]) -> int:
    """Клетки: > < ^ v — направление бесплатного перехода."""
    rows, cols = len(grid), len(grid[0])
    moves = {'>': (0, 1), '<': (0, -1), '^': (-1, 0), 'v': (1, 0)}
    directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]

    INF = float('inf')
    dist = [[INF] * cols for _ in range(rows)]
    dist[0][0] = 0
    dq = deque([(0, 0)])

    while dq:
        r, c = dq.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue

            # переход бесплатен, если совпадает со стрелкой
            cost = 0 if moves[grid[r][c]] == (dr, dc) else 1

            if dist[r][c] + cost < dist[nr][nc]:
                dist[nr][nc] = dist[r][c] + cost
                if cost == 0:
                    dq.appendleft((nr, nc))
                else:
                    dq.append((nr, nc))

    return dist[rows - 1][cols - 1]


grid = [
    '>>v',
    'v<<',
    '>>>',
]
print(min_flips(grid))   # 1

Где ещё встречается

Сетки с препятствиями, которые можно разрушить: проход по свободной клетке стоит 0, разрушение стены — 1.

Задачи «минимум изменений»: сколько рёбер нужно перенаправить, чтобы путь существовал.

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

Многоуровневые графы, где переход между слоями стоит единицу, а внутри слоя — ноль.

Общий признак: веса принимают ровно два значения, и меньшее из них равно нулю.

Обобщение: BFS по слоям

Приём расширяется на веса 0 и k (любое одинаковое положительное значение) — достаточно масштабировать.

Для небольшого набора весов 0..k существует алгоритм Диала: вместо дека берётся массив из k+1 очередей, и вершина кладётся в очередь по остатку расстояния. Сложность O(V·k + E) — выгодно, пока k мал.

Если весов много и они произвольные, вернуться к Дейкстре придётся в любом случае.

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

Проверка посещённости вместо расстояния. С обычным visited алгоритм сломается: вершину можно посетить повторно с меньшим расстоянием. Сравнивать нужно именно dist.

Все вершины в конец дека. Превращает алгоритм в обычный BFS, который на весах 0 и 1 работает неверно.

Использование списка вместо дека. list.insert(0, x) стоит O(n), и сложность вырождается в квадрат.

Отрицательные веса. Не поддерживаются. Ноль — минимально допустимый.

Что запомнить

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

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→