Почему Дейкстре нужны неотрицательные веса

Коротко

Доказательство прошлого урока держалось на одной фразе: «остаток пути имеет длину >= 0». Убери её - и всё рассыпается. Если в графе есть ребро отрицательного веса, вершина, уже объявленная окончательной, может ПОДЕШЕВЕТЬ позже, и классическая реализация со множеством «обработанных» вернёт неверный ответ; трёх вершин хватает, чтобы это показать. Ленивая реализация иногда исправляется сама, но гарантий не даёт и на плохих графах работает экспоненциально долго. Вывод практический: отрицательные веса - это другой алгоритм (Беллман-Форд, следующая глава), а не «Дейкстра, которая обычно работает». Зато в обратную сторону бывает приятно: если веса маленькие целые, Дейкстру можно ускорить, а при весах 0 и 1 - вообще заменить обходом с ДЕКОЙ за O(V + E).

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

Как думаешь, что именно сломает отрицательное ребро

Дейкстра фиксирует вершину с наименьшей оценкой и больше к ней не возвращается. Прежде чем читать дальше, придумай граф, где такое решение окажется преждевременным. Подсказка: нужна вершина, которая выглядит дешёвой сейчас, но становится ещё дешевле ПОСЛЕ того, как её зафиксировали.

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

Кассир, который выдаёт номерки по возрастанию суммы долга: «у кого долг меньше, тот и следующий». Пока все операции только увеличивают долг, порядок честен. Но стоит появиться операции, которая долг УМЕНЬШАЕТ, и правило ломается: человек, уже обслуженный как «самый дешёвый», после чужой операции оказывается ещё дешевле - а его уже отпустили.

Механизм: контрпример на трёх вершинах

s → a   вес 1
s → b   вес 2
b → a   вес −2        ← отрицательное ребро

истинные расстояния: dist[b] = 2, dist[a] = min(1, 2 + (−2)) = 0

Прогон классической Дейкстры со множеством «обработанных»:

извлекаем s (0) → фиксируем: dist[a] = 1, dist[b] = 2
извлекаем a (1) → ФИКСИРУЕМ a = 1  ← ошибка уже произошла, хотя ещё не видна
извлекаем b (2) → фиксируем b = 2
                  релаксируем b→a: 2 + (−2) = 0 < 1 …
                  но a уже в «обработанных» - улучшение отбрасывается
ответ: dist[a] = 1,  правильный ответ: 0

Ленивый вариант без множества обработанных (тот, что в прошлом уроке) на этом примере исправится - он просто положит (0, a) в кучу и обработает вершину ещё раз. Но это везение, а не гарантия: с отрицательными рёбрами вершины могут переобрабатываться многократно, и в худшем случае число переобработок растёт экспоненциально. Поэтому отрицательные веса - повод сменить алгоритм, а не надеяться.

А если веса маленькие целые? Тогда, наоборот, можно ускориться:

веса 0 и 1      : обход с ДЕКОЙ (0-1 BFS). Ребро веса 0 - кладём вершину в НАЧАЛО деки,
                  ребро веса 1 - в КОНЕЦ. Дека остаётся отсортированной по оценке,
                  куча не нужна: O(V + E)
веса 0..C целые : «вёдра» по расстояниям (алгоритм Дайала): массив из C·V+1 списков,
                  идём по нему слева направо: O(E + V·C)

Правило

Дейкстра требует НЕОТРИЦАТЕЛЬНЫХ весов: при отрицательном ребре уже зафиксированная вершина может подешеветь, и реализация со множеством обработанных вернёт неверный ответ (хватает трёх вершин). Ленивая реализация иногда исправляется, но гарантий не даёт и может работать экспоненциально. Отрицательные веса - это Беллман-Форд. Обратная сторона: при весах 0 и 1 куча не нужна вовсе - обход с декой (в начало по ребру веса 0, в конец по ребру веса 1) даёт O(V + E); при малых целых весах до C работает раскладка по вёдрам за O(E + V·C).

Разбор: где именно ломается доказательство

Вернёмся к доказательству из прошлого урока. Мы брали предполагаемый более короткий путь до u, находили на нём первое ребро x → y из обработанной части в необработанную и писали:

dist[y] <= dist[x] + w(x, y) = длина куска пути до y
длина всего пути = длина куска до y + длина остатка (y → ... → u)

И дальше ключевой шаг: остаток >= 0, значит длина всего пути >= dist[y], значит dist[y] < dist[u] - противоречие с выбором u как минимума.

Отрицательные рёбра убивают ровно эту строчку: остаток пути может быть отрицательным, и тогда весь путь оказывается КОРОЧЕ, чем его собственный кусок до y. Неравенство dist[y] < dist[u] больше не выводится, противоречия нет, и вершина u вполне могла быть зафиксирована рано.

Обрати внимание, что дело не в «отрицательных числах вообще», а именно в возможности удешевить путь его продолжением. Поэтому на графе с отрицательными весами, но без отрицательных ЦИКЛОВ задача всё ещё осмысленна (кратчайшие пути существуют) - её решает Беллман-Форд. А вот отрицательный цикл делает вопрос бессмысленным: крутясь по нему, путь можно удешевлять бесконечно. Об этом - следующая глава.

Разбор: обход с декой при весах 0 и 1

Задача, встречающаяся постоянно: на сетке часть переходов бесплатна (вес 0), часть стоит единицу (вес 1) - например, двигаться по коридору бесплатно, а ломать стену стоит одного удара. Куча для такого избыточна.

Идея: держим деку, из которой всегда берём элемент СПЕРЕДИ. Релаксируя ребро веса 0, кладём вершину в НАЧАЛО деки - её оценка равна оценке текущей вершины, значит она должна обрабатываться в ту же «волну». Ребро веса 1 кладёт вершину в КОНЕЦ - её оценка на единицу больше.

from collections import deque            # дека: очередь с двумя концами
dist = [INF] * V
dist[start] = 0
dq = deque([start])
while dq:
    v = dq.popleft()                     # берём СПЕРЕДИ
    for u, w in adj[v]:                  # w это 0 или 1
        if dist[v] + w < dist[u]:
            dist[u] = dist[v] + w
            if w == 0:
                dq.appendleft(u)         # в НАЧАЛО: та же волна
            else:
                dq.append(u)             # в КОНЕЦ: следующая волна

Инвариант: в деке лежат вершины не более чем с двумя разными оценками - d и d + 1, причём все d стоят раньше. Поэтому элемент спереди всегда имеет минимальную оценку - ровно то, что давала куча, но за O(1) вместо логарифма. Общая цена - O(V + E).

Тот же приём обобщается на целые веса от 0 до C. Вместо двух волн - много: заводят массив «вёдер», по ведру на каждое возможное расстояние, и идут по нему слева направо; вершина с оценкой d лежит в ведре номер d. Сколько нужно вёдер: путь содержит не больше V − 1 ребра, каждое весит не больше C, значит любое конечное расстояние лежит между 0 и C·(V − 1) - вёдер хватает C·V с запасом, отсюда и C·V + 1 в таблице. Это алгоритм Дайала (в английских книгах - Dial's algorithm, по фамилии автора, 1969), и на графах с маленькими весами (дороги в минутах, клетки с ценами 1-5) он обгоняет кучу: вместо логарифма на извлечение - переход к следующему ведру.

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

Первое: пускать Дейкстру на отрицательные веса «потому что данные хорошие» - ошибка проявится на редком входе и будет выглядеть как случайная. Второе: думать, что ленивая реализация «чинит» отрицательные веса: ответ она иногда даёт верный, но время может взорваться, и гарантии нет. Третье: пытаться обойти проблему, прибавив ко всем весам константу, чтобы они стали неотрицательными, - это МЕНЯЕТ задачу: пути с разным числом рёбер получают разную добавку, и кратчайший путь становится другим. (Правильная нормализация весов существует, она называется потенциалами Джонсона, и мы разберём её в главе про все пары.) Четвёртое: в обходе с декой класть вершину в конец при нулевом ребре - инвариант «сначала d, потом d+1» разрушится, и ответы поедут. Пятое: тащить вёдра при больших весах - память O(C·V) быстро становится неподъёмной.

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

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

Теперь сам

Граф: s→x = 4, s→y = 1, y→x = −3, x→t = 1. Что вернёт классическая Дейкстра (со множеством обработанных) и каков правильный ответ? А если ко всем весам прибавить 3, чтобы избавиться от отрицательного?

Ответ. Правильные расстояния: dist[y] = 1, dist[x] = min(4, 1 + (−3)) = −2, dist[t] = −1. Классическая Дейкстра: извлекаем s (0), релаксации дают dist[x] = 4, dist[y] = 1; извлекаем y (1) - фиксируем, релаксируем y→x: 1 + (−3) = −2 < 4 → dist[x] = −2 (пока всё хорошо); извлекаем x (−2) - фиксируем, релаксируем x→t: dist[t] = −1; извлекаем t. Здесь ответ случайно получился верным - потому что улучшение пришло ДО фиксации x. Но переставь веса: s→x = 1, s→y = 2, y→x = −2 - и Дейкстра зафиксирует x с оценкой 1, а правильный ответ 0. Именно это и значит «нет гарантии»: иногда везёт.

Теперь про прибавление тройки. Веса станут s→x = 7, s→y = 4, y→x = 0, x→t = 4. Считаем: путь s→x→t стоит 7 + 4 = 11, путь s→y→x→t стоит 4 + 0 + 4 = 8. Победил второй - и в исходной задаче он тоже был лучше (−1 против 5). Совпало? Да, но проверим другой пример: пусть s→t = 2 напрямую и s→a = 1, a→t = 0 - оба пути стоят 2 и 1 соответственно, второй лучше. Прибавим 3: первый путь 5, второй 4 + 3 = 7 - теперь лучше ПЕРВЫЙ. Ответ изменился, потому что добавка 3 умножилась на число рёбер: путь из двух рёбер получил +6, а из одного - только +3. Значит так нормализовать веса нельзя; правильный способ (потенциалы Джонсона) добавляет к каждому ребру РАЗНЫЕ поправки, устроенные так, чтобы длины всех путей между одной парой изменились одинаково.

Главное

Дейкстра требует неотрицательных весов, и это не формальность: доказательство корректности держится на шаге «остаток пути >= 0», а отрицательное ребро его отменяет - уже зафиксированная вершина может подешеветь. Классическая реализация со множеством обработанных на графе s→a=1, s→b=2, b→a=−2 возвращает dist[a] = 1 вместо 0; ленивая иногда исправляется сама, но гарантий нет и время может стать экспоненциальным. Отрицательные веса - это Беллман-Форд (следующая глава); а отрицательный ЦИКЛ делает задачу бессмысленной вовсе. Прибавить ко всем весам константу нельзя: добавка умножается на число рёбер и меняет ответ - правильная нормализация называется потенциалами Джонсона. В обратную сторону бывает выгода: при весах 0 и 1 кучу заменяет ДЕКА (ребро 0 - в начало, ребро 1 - в конец), и цена падает до O(V + E); при малых целых весах до C работают вёдра (алгоритм Дайала) за O(E + V·C).