Беллман-Форд: когда порядок выбрать нельзя

Коротко

Дейкстра выбирала порядок релаксаций умно и потому обходилась одним касанием каждого ребра. С отрицательными весами умный порядок недоступен - и Беллман-Форд поступает честно и грубо: релаксирует ВСЕ рёбра, и так V − 1 раз. Работает это из-за простого факта: кратчайший путь содержит не больше V − 1 рёбер (иначе в нём повторилась бы вершина, то есть появился цикл), а после k-го прохода правильно посчитаны все расстояния, достижимые путями из k рёбер. Цена - O(V·E): дороже Дейкстры, зато отрицательные веса не мешают. Плюс бесплатный бонус: если V-й проход всё ещё что-то улучшает, значит в графе есть отрицательный цикл - об этом следующий урок.

Если ты знаешь алгоритм, понимаешь, почему хватает V − 1 проходов, и можешь объяснить индукцию по числу рёбер пути, листай до «Теперь сам».

Как думаешь, сколько проходов нужно

Мы знаем: порядок релаксаций не влияет на правильность ответа, он влияет на то, сколько раз придётся их повторить. Прежде чем читать дальше, прикинь: если релаксировать ВСЕ рёбра подряд в произвольном порядке и повторять это снова и снова, когда можно остановиться? Подсказка: подумай, из скольких рёбер может состоять кратчайший путь.

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

Слух, расходящийся по компании. За один рабочий день каждый успевает рассказать всем, с кем общается, - но не дальше. Значит за день слух продвигается на одно «рукопожатие». Если в компании V человек, то через V − 1 день слух дойдёт до самого дальнего - дальше просто некуда, длиннее цепочки знакомств без повторов не бывает.

Механизм: V−1 проход по всем рёбрам

def bellman_ford(start):
    dist = [INF] * V
    dist[start] = 0
    for _ in range(V - 1):                 # V−1 проход
        changed = False
        for (u, v, w) in edges:            # релаксируем ВСЕ рёбра
            if dist[u] < INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed:                    # проход без единого улучшения -
            break                          # дальше ничего не изменится
    return dist

Три детали, каждая существенная.

Проверка dist[u] < INF. INF - обычное большое число, а не настоящая бесконечность, поэтому INF + (−3) < INF - правда, и без этой проверки недостижимые вершины начнут получать конечные оценки из ниоткуда. Пишут её и так, и в виде dist[u] != INF: пока оценка либо INF, либо меньше, это одно и то же условие. Форму < INF предпочитают потому, что она остаётся верной, даже если INF-вершину кто-то уже успел «улучшить» до INF − 3.

Досрочный выход. Если проход не изменил ни одной оценки, следующий тоже ничего не изменит - можно останавливаться. На практике это часто сокращает работу в разы; на худшем графе не помогает.

Порядок рёбер не важен для правильности, но влияет на скорость: удачный порядок «проталкивает» оценки дальше за один проход. Отсюда и практическое ускорение - вместо слепых проходов держать очередь вершин, чьи оценки изменились (такой вариант называют SPFA, от английского Shortest Path Faster Algorithm); в среднем он заметно быстрее, но в худшем случае остаётся O(V·E).

Правило

Беллман-Форд: V − 1 раз пройти по ВСЕМ рёбрам и релаксировать каждое. Цена O(V·E). Работает при любых весах, включая отрицательные, - лишь бы не было отрицательных циклов. После k-го прохода верны все расстояния, достижимые путями не более чем из k рёбер; кратчайший путь содержит не больше V − 1 рёбер, поэтому проходов хватает. Обязательна проверка dist[u] != INF, иначе недостижимые вершины получат конечные оценки. Проход без улучшений - можно выходить досрочно.

Разбор: почему хватает V−1 прохода

Докажем индукцией по числу рёбер пути. Утверждение: после k-го прохода для каждой вершины v оценка dist[v] не больше длины кратчайшего пути из s в v, содержащего не более k рёбер.

База, k = 0. Путь из нуля рёбер есть только до самого s, и dist[s] = 0 с самого начала.

Шаг. Пусть утверждение верно после k − 1 прохода, и пусть кратчайший путь до v из k рёбер проходит s → ... → u → v. Его кусок до u - это путь из k − 1 ребра, и он кратчайший среди таких (оптимальная подструктура), значит по предположению после (k−1)-го прохода dist[u] <= длина этого куска. На k-м проходе мы релаксируем ребро u → v (мы релаксируем ВСЕ рёбра!), и после этого dist[v] <= dist[u] + w(u, v) <= длина всего пути. Что и требовалось.

Сколько нужно проходов. Если отрицательных циклов нет, то среди кратчайших путей всегда есть путь БЕЗ повторяющихся вершин: цикл в пути имеет неотрицательную длину, и его выбрасывание путь не удлинит. Путь без повторов содержит не больше V вершин, то есть не больше V − 1 рёбер. Значит после V − 1 прохода все расстояния верны.

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

Разбор: считаем на графе с отрицательным ребром

Граф: s→a = 3, s→b = 5, a→t = 6, b→a = −4. Рёбра релаксируем в порядке записи.

старт: dist = {s:0, a:∞, b:∞, t:∞}

проход 1:
    s→a:  0 + 3 = 3 < ∞    → dist[a] = 3
    s→b:  0 + 5 = 5 < ∞    → dist[b] = 5
    a→t:  3 + 6 = 9 < ∞    → dist[t] = 9
    b→a:  5 + (−4) = 1 < 3 → dist[a] = 1   ← отрицательное ребро улучшило УЖЕ посчитанное
проход 2:
    a→t:  1 + 6 = 7 < 9    → dist[t] = 7   ← улучшение поехало дальше по пути
проход 3 (он же проверочный):
    ни одна релаксация не срабатывает → выходим досрочно

Ответ: dist = {s:0, a:1, b:5, t:7}. Смотри, что произошло на четвёртой строке первого прохода: оценка вершины a уже была посчитана и выглядела окончательной, а ребро b→a её УХУДШИТЬ не могло, зато улучшило. Именно это и отличает отрицательные веса: «посчитанная» вершина не окончательна, и улучшение потом расходится по всем путям, которые через неё идут - для этого и нужен второй проход.

Порядок записи рёбер решает, сколько проходов уйдёт. Запиши их «по течению» (s→b, b→a, a→t) - и всё сойдётся за один проход. Запиши в обратном порядке - каждый проход будет продвигать оценку ровно на одно ребро, и понадобятся все V − 1 = 3. Это и есть разница между «в среднем быстро» и «в худшем случае O(V·E)».

Сравни с Дейкстрой на этом же графе. Она берёт вершину с наименьшей оценкой: сначала a с оценкой 3, объявляет её окончательной и релаксирует a→t → dist[t] = 9. Только потом извлекается b с оценкой 5 и открывается путь s→b→a длиной 1 - но a уже закрыта, к t это улучшение не поедет. Дейкстра вернёт dist[t] = 9 вместо 7.

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

Первое: забыть проверку dist[u] != INF - недостижимые вершины получат оценки вида «бесконечность минус три», и ответ будет полным мусором. Второе: делать V проходов вместо V − 1 и считать это безобидным: лишний проход не портит ответ, но именно на нём ловят отрицательный цикл, и если не отличать «лишний проход» от «проверочного», обнаружение цикла потеряется. Третье: релаксировать рёбра только из «изменившихся» вершин, но забыть, что вершина могла измениться позже в том же проходе - в наивной реализации это безопасно, в оптимизированной надо аккуратно вести очередь. Четвёртое: применять Беллмана-Форда там, где хватает Дейкстры: на неотрицательных весах он в разы медленнее без всякой пользы. Пятое: ожидать, что досрочный выход спасёт на плохом графе - он помогает в среднем, а худший случай остаётся O(V·E).

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

Беллман-Форд - это ответ на вопрос «а если веса бывают отрицательными». Такие задачи встречаются: валютный арбитраж (прибыль как отрицательная стоимость), системы разностных ограничений вида x_j − x_i <= c (приём такой: каждое неравенство x_j − x_i <= c превращают в ребро i → j весом c, добавляют фиктивный старт с нулевыми рёбрами во все вершины и запускают Беллмана-Форда; полученные dist и есть решение системы, а отрицательный цикл означает, что неравенства противоречивы), планирование с бонусами и штрафами, вычисление «цены» с компенсациями. В сетях на нём стоит целое семейство протоколов дистанционно-векторной маршрутизации (RIP и родственники): каждый маршрутизатор знает только соседей и обменивается с ними оценками расстояний - это буквально распределённый Беллман-Форд, и его известная болезнь «счёт до бесконечности» - прямое следствие того, что оценки расходятся медленно, по одному ребру за обмен. А для инженера главный вывод проще: сначала выясни, какие у тебя веса, и лишь потом бери алгоритм.

Теперь сам

Граф: s→a = 1, a→b = −2, b→c = 1, c→a = 3, s→c = 5. Сколько проходов понадобится, если релаксировать рёбра в порядке записи? А если в обратном порядке?

Ответ. Истинные расстояния: dist[s] = 0, dist[a] = 1, dist[b] = −1, dist[c] = 0 (путь s→a→b→c стоит 1 − 2 + 1 = 0, что лучше прямого ребра весом 5).

Порядок записи. Проход 1: s→a: dist[a] = 1; a→b: 1 − 2 = −1 → dist[b] = −1; b→c: −1 + 1 = 0 → dist[c] = 0; c→a: 0 + 3 = 3 < 1? нет; s→c: 0 + 5 = 5 < 0? нет. Проход 2: ни одного улучшения → выход. Итого один содержательный проход плюс проверочный: рёбра шли «по течению», и оценка успела пробежать всю цепочку за раз.

Обратный порядок (s→c, c→a, b→c, a→b, s→a). Проход 1: s→c: dist[c] = 5; c→a: 5 + 3 = 8 → dist[a] = 8; b→c: dist[b] ещё ∞ - пропуск; a→b: 8 − 2 = 6 → dist[b] = 6; s→a: 0 + 1 = 1 < 8 → dist[a] = 1. Проход 2: s→c: без изменений; c→a: 5 + 3 не лучше 1; b→c: 6 + 1 = 7 < 5? нет; a→b: 1 − 2 = −1 < 6 → dist[b] = −1; s→a: без изменений. Проход 3: b→c: −1 + 1 = 0 < 5 → dist[c] = 0; остальные без изменений. Вершин здесь четыре, значит алгоритм и делает ровно V − 1 = 3 прохода - и все три понадобились. Итого три прохода вместо одного, и оценка продвигалась ровно на одно ребро за проход. Вот наглядная цена «слепого» порядка - и объяснение, почему на практике поверх Беллмана-Форда ставят очередь изменившихся вершин.

Главное

Беллман-Форд отказывается выбирать порядок: он V − 1 раз релаксирует ВСЕ рёбра, и этого хватает, потому что после k-го прохода верны все расстояния, достижимые путями из k рёбер (индукция по числу рёбер с опорой на оптимальную подструктуру), а кратчайший путь без отрицательных циклов содержит не больше V − 1 рёбер. Цена O(V·E) - дороже Дейкстры, зато отрицательные веса не мешают. Обязательна проверка dist[u] != INF: иначе недостижимые вершины получат оценки из ниоткуда. Проход без улучшений позволяет выйти досрочно, а порядок рёбер не влияет на правильность, но сильно влияет на число проходов - от одного до V − 1; отсюда практическое ускорение с очередью изменившихся вершин (SPFA), быстрое в среднем и такое же O(V·E) в худшем случае. На неотрицательных весах Беллман-Форд не нужен - там дешевле Дейкстра. Зато он даёт бесплатный бонус: V-й проход, если он всё ещё улучшает оценки, обнаруживает отрицательный цикл.