Отрицательные циклы: когда у задачи нет ответа

Если ты знаешь критерий «V-й проход улучшает ⇒ отрицательный цикл», умеешь восстановить сам цикл и понимаешь, почему при нём задача теряет смысл, листай до «Теперь сам».

Как думаешь, что должна вернуть программа

Граф: s→a = 1, a→b = −2, b→a = −1. Сумма весов цикла a→b→a равна −3. Прежде чем читать дальше, посчитай: чему равно кратчайшее расстояние от s до b? Пройди цикл один раз, потом два, потом десять - и посмотри, к чему всё идёт.

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

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

Механизм: V-й проход как детектор

def bellman_ford_with_check(start):
    dist = [INF] * V; dist[start] = 0
    prev = [-1] * V
    for _ in range(V - 1):
        for (u, v, w) in edges:
            if dist[u] < INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    # проверочный проход: всё честное уже посчитано
    for (u, v, w) in edges:
        if dist[u] < INF and dist[u] + w < dist[v]:
            return None, v, prev    # улучшение есть → отрицательный цикл, v внутри «зоны» цикла
    return dist, None, prev

Восстановление самого цикла - это продолжение той же функции (или отдельная, которой передали v и prev; массивы V, edges, prev те же):

x = v                      # вершина, улучшенная на проверочном проходе
for _ in range(V):
    x = prev[x]            # V шагов назад гарантированно вводят внутрь цикла
cycle = [x]
y = prev[x]
while y != x:
    cycle.append(y)
    y = prev[y]
cycle.reverse()            # вершины цикла по порядку

Почему V шагов: вершина v необязательно лежит на самом цикле - она может быть «ниже по течению», просто её оценка подешевела из-за него. Но каждый шаг по prev уводит на одно ребро назад по пути, а путь, улучшаемый бесконечно, обязан упираться в цикл; V шагов заведомо больше, чем длина «хвоста», поэтому после них мы точно внутри цикла.

Правило

Отрицательный цикл, достижимый из старта, означает, что кратчайших путей НЕ СУЩЕСТВУЕТ: длину можно уменьшать бесконечно. Критерий: после V − 1 прохода Беллмана-Форда сделать ещё один, ПРОВЕРОЧНЫЙ, - если он улучшает хоть одну оценку, отрицательный цикл есть. Сам цикл восстанавливают, пройдя V шагов назад по prev от улучшенной вершины (это гарантированно вводит внутрь цикла) и затем двигаясь до повтора. Цикл, НЕдостижимый из старта, на ответ не влияет - чтобы найти любой, запускают алгоритм из фиктивной вершины, соединённой рёбрами нулевого веса со всеми.

Разбор: почему ответа нет

Вернёмся к вопросу из начала: s→a = 1, a→b = −2, b→a = −1.

Путь s→a→b стоит 1 + (−2) = −1. Но можно крутануть цикл: s→a→b→a→b стоит 1 − 2 − 1 − 2 = −4. Ещё круг: −7. Каждый оборот отнимает 3. Значит для любого числа M найдётся путь дешевле −M, и минимума не существует - множество длин не ограничено снизу.

Поэтому вопрос «чему равно dist[b]» некорректен, и алгоритм, который вернёт какое-нибудь число, соврёт. Правильный ответ программы - признак «есть отрицательный цикл» (и, если полезно, сам цикл).

Заметь важную оговорку: значение имеет ДОСТИЖИМОСТЬ. Если отрицательный цикл висит в стороне и из старта в него не попасть, расстояния от старта прекрасно определены, и Беллман-Форд посчитает их верно; проверочный проход при этом ничего не улучшит, потому что оценки вершин цикла так и остались бесконечностями. А если надо найти отрицательный цикл ГДЕ УГОДНО в графе, добавляют фиктивную вершину с рёбрами нулевого веса во все остальные и запускают алгоритм из неё - тогда достижимо всё. Расстояния она не портит: рёбра ведут только ИЗ неё, поэтому ни один путь между старыми вершинами через неё не проходит, а новых циклов она не создаёт по той же причине - в неё не входит ни одно ребро. Единственное, что меняется: dist считается теперь не от s, а от фиктивного старта, и как расстояния эти числа читать уже нельзя - они нужны только затем, чтобы проверочный проход увидел цикл.

Разбор: ловим цикл проверочным проходом

Граф: s→a = 1, a→b = 2, b→c = −1, c→a = −3 (цикл a→b→c→a весит 2 − 1 − 3 = −2), V = 4, значит три обычных прохода и один проверочный. Рёбра в порядке записи.

проход 1: dist[a]=1, dist[b]=3, dist[c]=2, затем c→a: 2−3 = −1 < 1 → dist[a] = −1
проход 2: a→b: −1+2 = 1 < 3 → dist[b] = 1;  b→c: 0 < 2 → dist[c] = 0;  c→a: −3 < −1 → dist[a] = −3
проход 3: то же самое ещё раз - каждый проход отнимает вес цикла, то есть 2:
          dist[b] = −1, dist[c] = −2, dist[a] = −5
проверочный проход: a→b даёт −3 < −1 → УЛУЧШЕНИЕ ЕСТЬ → отрицательный цикл

Видно, как оценки уезжают вниз без остановки. Сдвиг одинаков у всех трёх вершин цикла и равен ровно весу цикла (−2): за проход оценка каждой вершины успевает пройти по кругу один раз, поэтому dist[b] падает с 1 до −1, dist[c] с 0 до −2, dist[a] с −3 до −5. Теперь восстановим сам цикл: улучшенная вершина - b; делаем V = 4 шага назад по prev (b → a → c → b → a) и оказываемся внутри цикла; дальше идём по prev до повтора и получаем a → c → b → a, то есть цикл a → b → c → a (в обратную сторону, останется развернуть).

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

Первое: сделать V проходов вместо V − 1 и не различать последний - тогда цикл не будет обнаружен, а оценки окажутся «какими-то», и ошибка станет молчащей. Второе: проверять цикл условием «оценка стала отрицательной» - неверно, отрицательные оценки бывают и без всяких циклов. Третье: объявлять цикл по любому улучшению в середине работы - улучшения идут постоянно, критерий только про ПРОВЕРОЧНЫЙ проход после V − 1 штатных. Четвёртое: искать отрицательный цикл в графе целиком, запуская алгоритм из одной вершины: цикл в другой компоненте останется незамеченным - нужна фиктивная вершина. Пятое: восстанавливать цикл, начиная прямо с улучшенной вершины, без V шагов назад: она может лежать вне цикла, и ты выпишешь «хвост» вместо цикла.

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

Самое известное применение - валютный арбитраж. Берут граф валют, вес ребра - минус логарифм курса; тогда произведение курсов превращается в сумму весов, а цепочка обменов с прибылью - ровно в отрицательный цикл. Поиск такого цикла Беллманом-Фордом и есть детектор арбитража. Второе применение - системы разностных ограничений (x_j − x_i <= c): они сводятся к кратчайшим путям, и отрицательный цикл означает, что система НЕСОВМЕСТНА, то есть ограничения противоречат друг другу. Так проверяют расписания и планировщики: «задача B должна начаться не позже, чем через 3 часа после A» - набор таких условий либо выполним, либо содержит замкнутое противоречие, и оно предъявляется как цикл. Третье - поиск ошибок в моделях: отрицательный цикл в графе стоимости часто означает не выгодную возможность, а ошибку в данных (перепутанный знак, дважды учтённая скидка).

Теперь сам

Граф: s→a = 2, a→b = 1, b→a = −4, b→t = 3. Есть ли отрицательный цикл, достижим ли он, и что должна вернуть программа? Что изменится, если вес b→a сделать равным −1?