Кратчайший путь ищут все, отрицательный цикл – единицы. Алгоритм Беллмана–Форда решает обе задачи одним проходом: считает расстояния и попутно ловит замкнутые схемы, приносящие выгоду из ничего. На бирже Uniswap V2 за 11 месяцев нашли 292 606 таких циклов. Основатель «Школы траблшутеров» Олег Брагинский и ученик Антон Бессарабов показывают, где прячутся петли, печатающие деньги.
Рис. 1. Круг b – d – c обходится в минус два: кратчайшего пути в таком графе не существует
Отрицательное ребро и отрицательный цикл
Систему описывает взвешенный орграф G(V, E). Вершины – ресурсы, валюты, точки маршрута, события. Веса рёбер – стоимость перехода, и она бывает отрицательной: подобранная аптечка, выгодный обмен, спуск с горы на электромобиле, требование успеть за три дня до срока.
Отрицательное ребро ломает алгоритм Дейкстры. Жадная логика предполагает, что дальше будет только дороже, и закрывает вершину навсегда, а крюк через отрицательное ребро приходит позже и оказывается выгоднее.
Ричард Беллман предложил решение в 1958 году на трёх страницах, применив принцип оптимальности. Лестер Форд и Делберт Фалкерсон свели теорию в книгу Flows in Networks (1962), где сформулирован ключевой для практики критерий: поток минимальной стоимости оптимален тогда и только тогда, когда в остаточной сети нет отрицательного цикла.
Алгоритм состоит из одной операции – релаксации ребра u – v весом w: если d[u] + w < d[v], записываем новое значение и запоминаем предшественника. Перебор всех рёбер повторяется V − 1 раз, потому что после k проходов верны все маршруты не длиннее k рёбер.
Отсюда бесплатный детектор. Если после V − 1 прохода контрольный перебор всё ещё что-то улучшает, в графе есть отрицательный цикл: маршрут длиннее V − 1 ребра выгоден только при наличии петли. Проверка стоит O(E), а указатели предшественников выдают сам цикл – список сделок, а не факт их существования.
Кратчайшего пути при этом не существует: круг по циклу всегда дешевле, стоимость равна минус бесконечности. Поиск кратчайшего простого пути в таком графе NP-труден, поэтому алгоритм не решает нерешаемое, а предъявляет находку.
Геймдизайн: эксплойт циклов
Экономика игры – сеть конвертаций, прибыль по цепочке равна произведению множителей. Логарифм переводит произведение в сумму: вес ребра принимают равным минус логарифму множителя, и прибыльная петля становится отрицательным циклом.
Проверим на типовой цепочке: купить бревно за 10 золота (множитель 0,1), распустить на три доски (3), продать каждую по 4 золота (4). Произведение 1,2 – каждый оборот даёт 20% прироста, и цикл крутится бесконечно.
Цена ошибки известна. Коровы в The Witcher 3 давали перезаряжаемый источник шкур быстрее расчётного и потребовали патча. Ошибки в Animal Crossing: New Horizons открыли бесконечные деньги и обрушили экономику острова гиперинфляцией.
Рис. 2. Ферма коров в The Witcher 3: шкуры возвращались быстрее, чем считал дизайнер
Формальные инструменты подтягиваются к практике. Фреймворк GEEvo Руппа и Эккерта (IEEE CEC, 2024) описывает экономику игры ориентированным графом с источниками, конвертерами, накопителями и стоками и балансирует её эволюционным алгоритмом. Проверка на отрицательные циклы встраивается в такой конвейер естественно.
Второй пример – навигация ботов. Если стоимостью перехода считать время минус ценность подобранного ресурса, коридор с аптечкой получает отрицательный вес. При респауне ресурса петля «сходил – вернулся» становится отрицательным циклом, и бот застревает в ней навсегда: по его модели поведение оптимально.
Лечение – расширение состояния: вершиной становится пара «место плюс флаг, подобран ли ресурс». Оговорка о границах: простой граф описывает конвертации «один вход – один выход», а рецепты вида «три доски плюс два гвоздя» образуют гиперрёбра и требуют линейной оптимизации.
Арбитраж: цикл, который печатает деньги
Курсы валют – тот же граф с логарифмированными весами. Цикл USD – EUR – GBP – USD с курсами 0,90, 0,85 и 1,35 даёт произведение 1,033: тысяча долларов возвращается тысячей тридцатью тремя.
Реальность вносит поправки. Комиссия включается прямо в вес и микроциклы отсекаются сами. Проскальзывание делает вес зависимым от объёма, а задержка обесценивает находку за миллисекунды.
Децентрализованные биржи убирают главное препятствие – риск исполнения. Цепочку из четырёх обменов там проводят одной транзакцией, которая либо проходит целиком, либо откатывается.
Анализ обменника Uniswap V2 обнаружил 292 606 циклических арбитражных транзакций за 11 месяцев более чем на 138 млн долларов. Механизм детекции построен на модифицированном алгоритме Мура–Беллмана–Форда.
Логистика: рекуперация и отмена циклов
Электротранспорт вернул отрицательные веса в дорожные графы: рекуперативное торможение на спуске возвращает энергию в батарею, поэтому ребро имеет отрицательную стоимость и классические ускорители маршрутизации неприменимы.
Рис. 3. Спуск возвращает энергию, перекос плана возвращает деньги – петлю ловят одним алгоритмом
Отрицательный цикл здесь невозможен: замкнутый маршрут с суммарным выигрышем энергии был бы вечным двигателем. Закон сохранения гарантирует отсутствие таких петель и позволяет заменить прямой перебор потенциалами Джонсона и быстрым Дейкстрой. Роль Беллмана–Форда – расчёт потенциалов и проверка допущения.
Второй слой – планирование перевозок. Отсутствие отрицательного цикла в остаточной сети служит критерием оптимальности плана, а найденный цикл – готовой инструкцией: перекинуть партию с одного маршрута на другой. Алгоритмы отмены циклов повторяют операцию, пока улучшения возможны.
Расписания: цикл как противоречие
Требования к проектам сводятся к разностным ограничениям вида xj − xi ≤ w, а те – к рёбрам графа. Система выполнима тогда и только тогда, когда отрицательных циклов нет; кратчайшие расстояния от фиктивного источника дают готовое расписание.
Пример узнаёт любой менеджер: проектирование 4 дня, сборка 5, релиз 3, дедлайн – 10 дней от старта. Цикл имеет вес −2. Алгоритм не просто отвечает «плана нет», а называет дефицит и предъявляет минимальный набор конфликтующих требований.
Рис. 4. Цикл весом минус два называет дефицит в двое суток и указывает, какое требование ослаблять
Формализм Simple Temporal Network – рабочая модель автоматического планирования от складских роботов до операций марсоходов. Планировщик перебирает тысячи состояний, поэтому проверку делают инкрементальной: структура δ-STN Микели (2022) переиспользует ранее вычисленные расстояния и решила все 638 тестовых задач, тогда как реализация на линейном программировании – 595.
Что изменилось за последние годы?
Классическая оценка O(V·E) держалась десятилетиями и пала в 2022 году: Бернстайн, Нанонгкай и Вульф-Нильсен построили почти линейный комбинаторный алгоритм, вышедший в Communications of the ACM в 2025 году. Динитц и Ицхак (2017) предложили гибрид с Дейкстрой для графов, где отрицательных рёбер немного. Для прикладных задач хватает тридцати строк классической версии с ранним выходом.
Практический порядок работы короткий:
выписать операции как рёбра, а стоимости – как веса, не пряча отрицательные
перевести мультипликативные величины в аддитивные через минус логарифм
добавить суперисточник: без него видны только циклы, достижимые из старта
задать порог, иначе округление вещественных чисел выдаст цикл из воздуха
восстановить сам цикл по указателям предшественников.
Поставьте проверку в регулярный контур: правка одной цены открывает цикл в другом конце системы. Отрицательный цикл – редкий случай, когда сбой алгоритма ценнее его результата. Расстояния подскажут, как добраться. Цикл подскажет, что систему уже можно ломать.