Дейкстра на целых весах: круг из C + 1 корзин и поразрядная куча

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

Как думаешь, сколько корзин на самом деле нужно

В уроке про веса 0 и 1 корзины Дайала уже появлялись: по корзине на каждое возможное расстояние, до C · V штук. На карте в 22 500 перекрёстков с весами до тысячи это двадцать два миллиона корзин - почти все пустые.

Прежде чем читать дальше, ответь себе: Дейкстра только что извлекла вершину с расстоянием d. Какие расстояния МОГУТ лежать в очереди в этот момент? Меньше d - нет, это уже извлечено. А насколько больше?

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

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

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

Механизм: две очереди с неубывающим минимумом

МОНОТОННОСТЬ: извлекли d → в очереди только расстояния из [d, d + C]
    (каждое лежащее там - чей-то d' + w, где d' ≤ d и w ≤ C)

КРУГ ДАЙАЛА: C + 1 корзин, расстояние x - в корзине x mod (C+1)
    стрелка tek идёт 0, 1, 2, ...; в корзине tek mod (C+1) лежат
    только вершины с расстоянием ровно tek (остальные разнесены)
    цена: E вставок + D + 1 осмотров; D - наибольший вставленный ключ
          создание C + 1 корзин добавляет O(C)

ПОРАЗРЯДНАЯ КУЧА: последний минимум m; корзины
    [m, m+1)  [m+1, m+2)  [m+2, m+4)  [m+4, m+8)  ...  ширины 1 1 2 4
    вставка: в корзину, куда попадает x
    извлечение: нижняя корзина пуста →
        взять первую непустую i, найти в ней минимум m',
        её отрезок разделить на корзины 0..i−1, начиная с m',
        переложить её элементы туда (корзины выше i не трогаем)

Почему у поразрядной кучи O(log(C+1)) переносов на элемент. Число корзин O(log(C+1)), в том числе при C=1. При перекладке элемент из конечной корзины i попадает в корзину с меньшим номером: её ширина не больше суммарной ширины нижних корзин. У последней неограниченной корзины используется окно ключей длины C: после переноса минимума все её элементы тоже помещаются ниже. Номер только убывает. Уменьшая ключ существующей вершины, ищем новую корзину от прежнего номера вниз. Все такие шаги за жизнь вершины суммарно ограничены числом корзин.

Правило

При целых весах 1..C очередь Дейкстры монотонна: в ней только расстояния из [d, d + C], где d - последний извлечённый минимум. Круг из C + 1 корзин по остатку d mod (C + 1) даёт O(E + C + D) с памятью O(V + E + C) в показанной версии с устаревшими записями; здесь D - наибольший вставленный ключ. Если при уменьшении ключа удалять старую запись за O(1), памяти достаточно O(V+C). Поразрядная куча держит корзины ширины 1, 1, 2, 4, … от последнего минимума и делит первую непустую при опустошении нижней. При единственной записи вершины, удалении за O(1) и поиске корзины от её прежнего номера вниз итоговая цена O(E + V·log(C+1)), без прохода по всем ключам до D.

Разбор: круг на четыре корзины

веса 1..3 → C + 1 = 4 корзины. Извлекли вершину s с d = 10.
её соседи получили 11, 13, 12 → корзины
    11 mod 4 = 3,  13 mod 4 = 1,  12 mod 4 = 0

корзина:   0       1       2       3
         [12]    [13]    [10]    [11]

стрелка 10 (корзина 2): извлекли s, соседи разнесены по кругу.
стрелка 11 → корзина 3: извлекаем 11.
стрелка 12 → корзина 0: извлекаем 12.  13 → корзина 1: извлекаем 13.

Корзина 1 содержит 13, а могла бы содержать 9 или 17 - но 9 уже извлечено, а 17 в очереди быть не может, пока стрелка стоит на 10 или выше: 17 > 10 + 3. Ровно монотонность и делает круг однозначным.

Разбор: три очереди на сетке 150 × 150

Программа строит сетку из 22 500 перекрёстков с весами улиц от 1 до 1000, считает кратчайшие расстояния от угла тремя очередями - кучей, кругом Дайала и поразрядной кучей - и сверяет ответы.

В поразрядной очереди массивы prev, nxt задают двусвязные списки вершин внутри корзин, head - начало каждого списка, bucket[v] - текущий номер корзины вершины. Это ссылки по индексам, поэтому remove и put работают за O(1). Уменьшение ключа удаляет старую запись вместо создания копии. Счётчик count показывает число вершин в очереди, не требуя просмотра всех корзин на каждом шаге. Круг Дайала для сравнения оставлен с копиями: его очередь может занимать O(E), а не O(V) памяти. Чтобы получить O(V+C), старую запись нужно удалять и там; подойдёт такая же организация корзин через индексные списки.

import heapq
import random

rng = random.Random(14)
N, C = 150, 1000                     # сетка N×N, веса рёбер 1..C
V = N * N
sosedi = [[] for _ in range(V)]
for r in range(N):
    for c in range(N):
        v = r * N + c
        for u in (v + 1 if c + 1 < N else -1,
                  v + N if r + 1 < N else -1):
            if u >= 0:
                w = rng.randint(1, C)
                sosedi[v].append((u, w))
                sosedi[u].append((v, w))
INF = float("inf")


def kucha():
    dist, h, shagi = [INF] * V, [(0, 0)], 0
    dist[0] = 0
    while h:
        d, v = heapq.heappop(h)
        shagi += 1                   # извлечение
        if d > dist[v]:
            continue
        for u, w in sosedi[v]:
            if d + w < dist[u]:
                dist[u] = d + w
                heapq.heappush(h, (d + w, u))
                shagi += 1           # вставка
    return dist, shagi


def dajal():                         # C + 1 корзин по кругу
    dist = [INF] * V
    dist[0] = 0
    korz = [[] for _ in range(C + 1)]
    korz[0].append(0)
    tek, ostalos, shagi = 0, 1, 0
    while ostalos:
        b = korz[tek % (C + 1)]
        shagi += 1                   # осмотр корзины
        while b:
            v = b.pop()
            ostalos -= 1
            if dist[v] != tek:
                continue             # устаревшая запись
            for u, w in sosedi[v]:
                if tek + w < dist[u]:
                    dist[u] = tek + w
                    korz[dist[u] % (C + 1)].append(u)
                    ostalos += 1
        tek += 1
    return dist, shagi


def porazryadnaya():
    K = C.bit_length() + 2
    gr = [0] + [2 ** (j - 1) for j in range(1, K)] + [INF]
    head = [-1] * K
    prev, nxt, bucket = [-1] * V, [-1] * V, [-1] * V

    def remove(v):
        i, a, b = bucket[v], prev[v], nxt[v]
        if a == -1:
            head[i] = b
        else:
            nxt[a] = b
        if b != -1:
            prev[b] = a
        bucket[v] = -1

    def put(v, i):
        bucket[v], prev[v], nxt[v] = i, -1, head[i]
        if head[i] != -1:
            prev[head[i]] = v
        head[i] = v

    dist, shagi, count = [INF] * V, 0, 1
    dist[0] = 0
    put(0, 0)
    while count:
        if head[0] == -1:
            i = 1
            while head[i] == -1:
                i += 1
            nodes = []
            v = head[i]
            while v != -1:
                nodes.append(v)
                v = nxt[v]
            m, top = min(dist[v] for v in nodes), gr[i + 1]
            gr[0] = m
            for j in range(1, i + 1):
                gr[j] = min(m + 2 ** (j - 1), top)
            for v in nodes:
                remove(v)
                j = i - 1
                while dist[v] < gr[j]:
                    j -= 1
                put(v, j)
                shagi += 1
        v = head[0]
        remove(v)
        count -= 1
        for u, w in sosedi[v]:
            if dist[v] + w < dist[u]:
                dist[u] = dist[v] + w
                i = bucket[u]
                if i == -1:
                    i = K - 1
                    count += 1
                else:
                    remove(u)
                while dist[u] < gr[i]:
                    i -= 1
                put(u, i)
                shagi += 1
    return dist, shagi

d1, s1 = kucha()
d2, s2 = dajal()
d3, s3 = porazryadnaya()
assert d1 == d2 == d3
print(f"вершин {V}, веса 1..{C}, самое дальнее {max(d1)}")
print(f"куча: операций {s1}, каждая - до log2 размера кучи")
print(f"Дайал: осмотрено корзин {s2}")
print(f"поразрядная: раскладок {s3}, на вершину {s3 / V:.1f},"
      f" разрядов в C = {C.bit_length()}")

вершин 22500, веса 1..1000, самое дальнее 68642
куча: операций 59557, каждая - до log2 размера кучи
Дайал: осмотрено корзин 68845
поразрядная: раскладок 122198, на вершину 5.4, разрядов в C = 10

Все три дали одинаковые расстояния. Круг Дайала держал 1001 корзину вместо двадцати двух миллионов и осмотрел их 68845 раз: последний просмотренный ключ 68844, хотя наибольшее итоговое расстояние 68642. Разница вызвана устаревшими записями, оставшимися после уменьшения расстояний. Поразрядная очередь выполнила 122198 вставок, обновлений и переносов, в среднем 5,4 на вершину. Счётчик включает и обновления, которых O(E), и переносы, которых O(V·log(C+1)). Это число событий в очереди, а не измерение времени: операции у трёх реализаций разные.

Поиск первой непустой корзины и пересчёт границ стоят O(log(C+1)) на извлечение минимума. Минимумов не больше V. При поиске корзины номер вершины только уменьшается, так что все проверки границ и переносы тоже дают O(V·log(C+1)). Просмотр рёбер и обновления ключей добавляют O(E). Если бы мы каждый раз искали корзину с нулевого номера или сохраняли копии старых записей, это доказательство к такому коду не относилось бы.

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

Первая ошибка - круг меньше C + 1: две вершины с расстояниями d и d + C попадают в одну корзину и извлекаются как одинаково близкие. Вторая - корзины для нецелых весов: круг держится на том, что между соседними расстояниями нет промежуточных значений. Третья - в поразрядной куче пересчитать границы ВСЕХ корзин от нового минимума: элементы в корзинах выше i окажутся не на своих местах, и очередь вернёт не минимум. Четвёртая - забыть про устаревшие записи: вершина, чьё расстояние уменьшилось, остаётся в старой корзине, и её надо пропускать при извлечении.

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

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

Теперь сам

Поразрядная куча, последний минимум m = 20. Корзины: [20,21) [21,22) [22,24) [24,28) [28,36). В ней лежат 30, 25, 33. Куда они попадут и что произойдёт при следующем извлечении?