Алгоритм Беллмана-Форда: пути с отрицательными весами

Алгоритм Беллмана-Форда - это способ найти кратчайшие пути от одной вершины графа до всех остальных, когда в графе есть рёбра с отрицательными весами. Имена в названии - Ричард Беллман и Лестер Форд: они независимо описали схему в 1956-1958 годах. В отличие от Дейкстры, Беллман-Форд корректно работает при отрицательных весах и умеет обнаруживать отрицательные циклы - пути, по которым можно бесконечно уменьшать сумму. Платой за это является сложность $O(V \cdot E)$: алгоритм медленнее Дейкстры, но универсальнее.

Зачем нужен - где Дейкстра ломается

Дейкстра - жадный алгоритм. На каждом шаге он берёт вершину $u$ с минимальным текущим $d[u]$ и считает, что её расстояние больше уже не улучшится. Это рассуждение справедливо только при неотрицательных весах: добавляя к $d[u]$ новое ребро, мы можем только увеличить сумму.

Если в графе есть отрицательное ребро, рассуждение разваливается. Минимальный пример - три вершины:

A → B (вес 5)
A → C (вес 4)
C → B (вес -3)

Дейкстра, начиная из $A$, сначала «закрепит» $B$ со значением $5$, потому что это меньше, чем $4$ у $C$. После этого она уже не вернётся к $B$, хотя реальный кратчайший путь - $A \to C \to B$ длиной $4 + (-3) = 1$. Ответ окажется неверным. Беллман-Форд же ничего не закрепляет преждевременно и спокойно найдёт $d[B] = 1$.

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

Главная идея - динамическая релаксация

Беллман-Форд опирается на простое наблюдение. Кратчайший путь из $s$ в любую вершину без повторений содержит не более $V - 1$ рёбер (иначе по принципу Дирихле в нём была бы вершина дважды и цикл, который можно выбросить). Значит, если повторить операцию релаксации всех рёбер графа $V - 1$ раз, любое корректное кратчайшее расстояние успеет «дойти» до своей вершины.

Релаксация ребра $(u, v, w)$ - то же, что у Дейкстры:

$\text{если } d[u] + w < d[v], \text{ то } d[v] \leftarrow d[u] + w$

Разница в порядке. Дейкстра выбирает «лучшую» вершину для расслабления по очереди и обрабатывает каждую один раз. Беллман-Форд тупо проходит по всем рёбрам в произвольном порядке и повторяет такой проход $V - 1$ раз. За счёт повторов отрицательные ребра успевают «доехать» до своих потомков.

После первой итерации точно посчитаны кратчайшие пути из одного ребра. После второй - из двух рёбер. После $k$-й - из не более чем $k$ рёбер. После $V - 1$-й - все, какие возможны.

Псевдокод

function bellman_ford(V, E, s):
    d[s] = 0
    d[v] = ∞   для всех v ≠ s

    Повторить V - 1 раз:
        для каждого ребра (u, v, w) ∈ E:
            если d[u] + w < d[v]:
                d[v] = d[u] + w

    # Проверка отрицательного цикла
    для каждого ребра (u, v, w) ∈ E:
        если d[u] + w < d[v]:
            return "Отрицательный цикл достижим из s"

    return d

Восстановление пути устроено как и у Дейкстры: в момент успешной релаксации запоминаем $prev[v] = u$, а потом идём от целевой вершины назад до $s$.

На бумажке руками такой обход можно прогнать только на маленьких графах из 4-5 вершин. Опиши свой граф ниже, выбери режим - и собранный запрос откроет чат с пошаговой трассировкой: что в массиве $d[v]$ после каждой итерации, есть ли отрицательный цикл и, если есть, какие вершины в него входят.

Обнаружение отрицательных циклов

Если в графе есть цикл, сумма весов в котором отрицательна, понятия «кратчайшего пути» в строгом смысле не существует - каждый новый обход цикла уменьшает суммарную длину, и инфимум равен $-\infty$. Беллман-Форд умеет такой цикл обнаружить.

Идея проверки. После $V - 1$ итераций все корректные кратчайшие пути уже стабилизировались - никакая релаксация не должна давать улучшения. Если на $V$-й итерации хоть одно ребро $(u, v, w)$ всё ещё уменьшает $d[v]$, значит, мы упёрлись в отрицательный цикл, достижимый из $s$. Какая именно вершина лежит на цикле - можно восстановить, пройдя $V$ раз по $prev$ от $v$: за столько шагов гарантированно попадём на сам цикл, а дальше обходом извлечём его вершины.

В практике эта проверка ценнее самих кратчайших путей. Классический пример - arbitrage detection в финансовых сетях. Вершины - валюты, рёбра - обменные курсы. Если за вес ребра $(A, B)$ взять $-\log r(A, B)$, где $r$ - курс, то произведение курсов по циклу превращается в сумму весов. Отрицательный цикл по этим весам означает, что произведение курсов по кругу больше единицы - то есть из 1 рубля через $A \to B \to C \to A$ получается больше 1 рубля. Это и есть арбитражная возможность. Беллман-Форд её ищет за полиномиальное время.

Подробный пример

Граф из пяти вершин с одним отрицательным ребром:

s → A (вес  6)
s → B (вес  7)
A → C (вес  5)
A → B (вес  8)
A → D (вес -4)
B → C (вес -3)
B → D (вес  9)
C → B (вес -2)
D → s (вес  2)
D → C (вес  7)

Начальное состояние: $d[s] = 0$, остальные - $\infty$. Будем обходить рёбра в порядке, в котором они выписаны.

Итерация 1. $d[A] = 6, d[B] = 7, d[C] = 11, d[D] = 2$ (через $A$). Из $B$: $d[C] = \min(11, 7-3) = 4$. Из $D$: $d[s] = \min(0, 2+2) = 0$, $d[C] = \min(4, 2+7) = 4$.

Итерация 2. Из $C$ релаксируется $d[B] = \min(7, 4-2) = 2$. Из $B$ потом $d[C] = \min(4, 2-3) = -1$, $d[D] = \min(2, 2+9) = 2$. Из $A$ снова $d[D] = -2$ (через $6 + (-4)$).

Итерация 3. Из $C$: $d[B] = -3$. Из $B$: $d[C] = -6$, и так далее.

Заметим, что значения продолжают уменьшаться. Дойдя до $V - 1 = 4$-й итерации, мы получим конкретный набор $d[\cdot]$. На пятой проверочной итерации релаксации всё ещё проходят - потому что цикл $B \to C \to B$ имеет суммарный вес $-3 + (-2) = -5 < 0$. Алгоритм сообщит об отрицательном цикле и не вернёт расстояний. Это и есть штатная работа.

Если бы ребра $C \to B$ не было (или его вес был бы $+2$, а не $-2$), цикла бы не существовало, и алгоритм за $V - 1 = 4$ итерации сошёлся бы к корректному набору расстояний.

Сложность и сравнение с Дейкстрой

Внешний цикл выполняется $V - 1$ раз, внутри - проход по всем $E$ рёбрам. Итого:

$T_{BF} = O(V \cdot E)$

Для сравнения, Дейкстра с двоичной кучей:

$T_{D} = O((V + E)\log V)$

В плотных графах ($E \approx V^2$) Беллман-Форд работает за $O(V^3)$, Дейкстра - за $O(V^2 \log V)$. В разреженных ($E \approx V$) - $O(V^2)$ против $O(V \log V)$. Беллман-Форд почти всегда хуже по скорости. Но он умеет то, чего Дейкстра не умеет.

Существует улучшение - SPFA (Shortest Path Faster Algorithm): вместо слепого обхода всех рёбер на каждой итерации поддерживается очередь вершин, у которых $d[\cdot]$ только что изменилось - именно их рёбра имеет смысл расслаблять дальше. В среднем SPFA работает существенно быстрее $O(VE)$, хотя в худшем случае оценка та же. На случайных графах SPFA обычно обгоняет даже Дейкстру.

Применения

• Маршрутизация в сетях. Протокол RIP (Routing Information Protocol) - классический distance-vector протокол, опирается на Беллмана-Форда. Каждый маршрутизатор хранит вектор расстояний до всех узлов и обновляет его по обновлениям соседей. RIP ограничен 15 хопами как раз потому, что без ограничения отрицательные обновления могут «гулять» по сети.
• Arbitrage detection. В валютных парах, как мы разобрали выше, отрицательный цикл = арбитражная возможность.
• Линейное программирование. В задачах LP с ограничениями вида $x_v - x_u \leq w_{uv}$ (системы разностных ограничений) Беллман-Форд находит допустимое решение либо доказывает его отсутствие.
• Алгоритм Джонсона. Для задачи о всех парах кратчайших путей в графе с отрицательными весами Джонсон сначала запускает Беллмана-Форда, чтобы перевзвесить рёбра в неотрицательные, а потом $V$ раз - Дейкстру. Итоговая сложность $O(VE + V^2 \log V)$ - лучше, чем прямой Флойд-Уоршалл $O(V^3)$, на разреженных графах.

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

• Делают $V$ итераций вместо $V - 1$. Корректных итераций ровно $V - 1$; $V$-я нужна только для проверки отрицательного цикла. Лишний проход не вреден, но запутывает: непонятно, считаешь ты ещё пути или уже проверяешь цикл.
• Игнорируют недостижимые вершины. Если $d[u] = \infty$, выражение $d[u] + w$ в большинстве языков переполнится и станет отрицательным. Сравнение нужно защищать: if d[u] != ∞ and d[u] + w < d[v].
• Считают, что любой отрицательный цикл будет найден. Беллман-Форд обнаружит только циклы, достижимые из стартовой вершины. Для поиска любого отрицательного цикла в графе можно добавить виртуальную вершину $s'$ с рёбрами $s' \to v$ нулевого веса ко всем $v$ и запустить из $s'$.
• Путают с Флойдом-Уоршаллом. Беллман-Форд - single-source ($s \to$ все). Флойд-Уоршалл - all-pairs (все $\to$ все), за $O(V^3)$.
• Применяют к ориентированному циклу, считая его обычным ребром. Цикл $A \to B \to A$ с весами $1$ и $-3$ - отрицательный. На неориентированном графе любое отрицательное ребро $\{u, v\}$ автоматически даёт отрицательный цикл $u \to v \to u$, поэтому Беллман-Форд на неориентированных графах с отрицательными весами почти всегда бесполезен.

FAQ

В чём принципиальная разница с алгоритмом Дейкстры? Дейкстра жадно фиксирует вершину с минимальным $d$ и больше к ней не возвращается - это даёт скорость $O((V+E)\log V)$, но ломается при отрицательных весах. Беллман-Форд ничего не фиксирует, повторяет релаксацию $V-1$ раз и работает корректно при любых весах, кроме отрицательных циклов.

Можно ли получить кратчайший путь, а не только длину? Да, как у Дейкстры: завести массив $prev[v]$, обновлять его в момент релаксации, в конце восстанавливать путь от целевой вершины назад до $s$.

Что делать, если в графе есть отрицательный цикл, но мне всё равно нужны кратчайшие пути для остальных вершин? Запустить Беллмана-Форда как обычно. Вершины, в которые нельзя «дойти через цикл», сохранят корректные значения. Вершины, на пути к которым лежит отрицательный цикл, нужно пометить специальным флагом $-\infty$ - это делается отдельным BFS/DFS из вершин, для которых на $V$-й итерации сработала релаксация.

Коротко

Беллман-Форд за $V - 1$ проход по всем рёбрам находит кратчайшие пути из стартовой вершины во все остальные при любых весах, включая отрицательные. На $V$-й итерации он же обнаруживает отрицательные циклы, достижимые из старта. Сложность $O(V \cdot E)$ хуже Дейкстры, но цена честная: при отрицательных весах Дейкстра попросту неверна. Главные практические сценарии - distance-vector маршрутизация (RIP), arbitrage detection в финансовых сетях и подготовительный шаг в алгоритме Джонсона.