Алгоритм Беллмана — Форда
Также: Bellman–Ford algorithm · Bellman–Ford–Moore · алгоритм Беллмана — Форда — Мура · SPFA · поиск отрицательного цикла · negative cycle detection
Кратчайшие пути, когда у рёбер бывают отрицательные длины: все рёбра проверяются раунд за раундом, и после k раундов известны лучшие пути не длиннее k рёбер. Если улучшения не кончаются, в графе есть цикл отрицательной длины — на курсах валют это круг обменов, который возвращает больше, чем было.
9 октября 2026 года Нацбанк объявил, что евро стоит 502,05 тенге, рэнд (ZAR) — 26,91 тенге, а песо (MXN) — 24,89. В тот же день ЕЦБ объявил, что за евро дают 18,527 рэнда или 20,395 песо. Купим на миллион тенге рэндов, за рэнды — евро, за евро — песо, а песо продадим обратно за тенге. Получится 1 018 192 тенге. Круг можно повторить, и миллион будет расти без конца. Ниже — все курсы этого дня и алгоритм, который такие круги находит.
Посмотрите, что происходит с первой строкой под картинкой. Пока курсы берутся у одного источника — только у Нацбанка или только у ЕЦБ, — выгодного круга нет: все курсы идут через тенге или через евро и согласованы между собой. Стоит взять оба источника, и сумма в тенге начинает расти от раунда к раунду. Подвиньте ползунок комиссии: если каждый обмен стоит 0,45 %, выгодных кругов не остаётся.
Идея
Сначала превратим обмены в путь. Курс — множитель: за единицу валюты A дают r единиц валюты B, и сумма после нескольких обменов — произведение курсов. Логарифм превращает произведение в сумму, а «больше» — в «меньше», если взять его со знаком минус. Положим длину ребра A → B равной −log r. Тогда самый выгодный обмен — кратчайший путь, а круг, возвращающий больше, чем было, — цикл отрицательной длины.
Длины получаются и положительными, и отрицательными, и Дейкстра здесь врёт: она объявляет расстояние окончательным, а отрицательное ребро потом его уменьшает. Нужен алгоритм, который не делает преждевременных выводов.
Проверяйте все рёбра подряд и улучшайте расстояния, где можно, — это один раунд. После k раундов известны кратчайшие пути из не более чем k рёбер. Кратчайший путь без циклов содержит не больше V − 1 ребра, поэтому V − 1 раундов хватает. Если и V-й раунд что-то улучшил, в графе есть цикл отрицательной длины, и кратчайших путей нет: каждый оборот по циклу делает путь ещё короче.
Каждая проверка — та же релаксация, что у Дейкстры. Разница в порядке: Дейкстра выбирает, какую вершину обработать следующей, и потому обрабатывает каждую один раз. Беллман — Форд ничего не выбирает и просто повторяет всё, пока не перестанет меняться.
Раунды по шагам
Вот ловушка из статьи о Дейкстре — дорога C → B длиной −3 — и ещё одна дорога, D → E. Строки таблицы — расстояния от A после каждого раунда.
При неудачном порядке рёбер новость о коротком пути проходит одно ребро за раунд: сначала до B, потом до D, потом до E, и нужно четыре раунда. При удачном — когда рёбра стоят в порядке путей — хватает одного. Ответ от порядка не зависит, зависит только время. Теперь включите дорогу E → C длиной −1: круг C → B → D → E → C имеет длину −3 + 1 + 2 − 1 = −1, и пятый раунд снова что-то улучшает. При пяти вершинах это означает отрицательный цикл.
Почему это верно
Если в графе нет цикла отрицательной длины, достижимого из старта, то после k раундов расстояние до каждой вершины не больше длины кратчайшего пути к ней из не более чем k рёбер, а после V − 1 раундов равно длине кратчайшего пути. Если такой цикл есть, улучшения не прекращаются ни в каком раунде.
Первое — индукция по k. Пусть кратчайший путь из не более чем k + 1 ребра к v кончается ребром (u, v). Его начало до u — путь не длиннее k рёбер, и после k раундов dist[u] не больше его длины. В раунде k + 1 ребро (u, v) проверяется, и dist[v] становится не больше длины всего пути. Расстояния никогда не опускаются ниже настоящих: каждое число dist — длина какого-то реального пути. Без отрицательных циклов кратчайший путь можно взять простым, а в простом пути не больше V − 1 ребра.
Второе. Пусть цикл v0, v1, …, vm = v0 имеет отрицательную длину и достижим, а раунд прошёл без улучшений. Тогда для каждого ребра цикла dist[vi] ≤ dist[vi−1] + wi. Сложим эти m неравенств: суммы dist слева и справа одинаковы, и остаётся 0 ≤ w1 + … + wm < 0. Противоречие.
Остаётся достать сам цикл. Каждое улучшение запоминает, откуда пришли: parent[v] = u. Если V-й раунд улучшил вершину x, то цепочка parent от x назад не может закончиться на старте за V − 1 шаг — иначе это был бы путь, найденный уже к раунду V − 1, — и где-то зацикливается. Шагнём от x назад V раз: так мы точно сойдём с хвоста на сам цикл. Потом идём по parent, пока не вернёмся в ту же вершину.
Доказательство заодно говорит, что Беллман — Форд — динамика: состояние «вершина и число рёбер», переход — одно ребро. Если копировать массив расстояний перед раундом, после k раундов будет известно ровно лучшее «не больше k рёбер». Без копии раунд иногда успевает больше — для кратчайших путей это только плюс, а когда число шагов ограничено условием, это ошибка. Ровно об этом вторая задача.
Код
Классический вариант: список рёбер, раунды до первого раунда без изменений и поиск цикла по parent. Демо — те же пять перекрёстков.
А это курсы 9 октября. Программа строит граф из курсов Нацбанка, ЕЦБ, обоих вместе и из таблицы ЕЦБ, пересчитанной к каждой валюте, ищет выгодный круг и двоичным поиском — наименьшую комиссию, при которой его нет.
the ECB table re-based and rounded: TRY -> USD -> TRY gives +0.018% pairs that come back with more: 223 of 435, the best IDR -> RON -> IDR +1.299% a fee of 0.64% per exchange removes every cycle both sources: KZT -> ZAR -> EUR -> MXN -> KZT 1000000 KZT -> 1018192 KZT a fee of 0.45% per exchange removes every cycle
Откуда берётся «прибыль»
У программы три находки, и ни одна не делает богаче.
Один источник — согласованные курсы. Нацбанк объявляет курс каждой валюты к тенге, ЕЦБ — к евро. Любой круг обменов внутри одного источника проходит через центр туда и обратно, и произведение курсов на нём ровно 1. Беллман — Форд останавливается после второго раунда: выгодного круга нет.
Тот же источник, но с округлением. Сервис Frankfurter пересчитывает таблицу ЕЦБ к любой базовой валюте и округляет курсы, и у совсем маленьких курсов остаётся две-три значащие цифры: рупия (IDR) к лею (RON) получается 0,00027, а лей к рупии — 3751,83, и «купить и тут же продать» даёт +1,3 %. В таблице из 435 пар таких пар 223. Это не прибыль, а следы округления, и Беллман — Форд честно находит их первыми.
Два источника — два разных момента. ЕЦБ сверяет курсы днём, около 14:10 по своему местному времени, Нацбанк устанавливает курс тенге по своей методике и в своё время. Через рэнд евро обходится в 26,91 · 18,527 = 498,56 тенге, через песо его можно продать за 24,89 · 20,395 = 507,63 тенге, а у самого Нацбанка евро стоит 502,05. Разница в 1,8 % — и есть круг из сцены. Купить по такому курсу нельзя: справочные курсы публикуются для сведения, и ЕЦБ прямо не рекомендует использовать свои для сделок. Настоящий обменный пункт берёт разницу между покупкой и продажей, и при комиссии 0,45 % за обмен круг исчезает.
Отсюда и вывод о самом методе. Отрицательный цикл в графе курсов означает несогласованность курсов, а не готовый способ заработать. На биржах такие несогласованности бывают настоящими, но живут доли секунды и учитывают комиссии и объёмы, которых в справочных таблицах нет.
Без запаса в сравнении Беллман — Форд находит «арбитраж» и в курсах одного Нацбанка. Курс QAR к тенге — 123,17, обратный — 1/123,17, и их произведение ровно 1. Но −log 123,17 − log(1/123,17) в плавающей точке равно −8,9 · 10−16, и без запаса этот круг выглядит выгодным. Таких пар среди 48 курсов семь. Поэтому в листинге улучшение засчитывается, только если оно больше 10−12.
Сколько это стоит
Каждый раунд проверяет все E рёбер, раундов не больше V: O(V · E) времени и O(V) памяти. С ранней остановкой раундов столько, сколько рёбер в самом длинном из кратчайших путей, плюс один. На дорожной решётке это порядка её стороны, √V, и время — около E · √V. Замер на решётках со случайными длинами от 1 до 9 и перемешанным порядком рёбер, рядом с Дейкстрой:
Все раунды — наклон около 2, как и обещает V · E при E ≈ 2V. С ранней остановкой — около 1,6, близко к V1,5. Дейкстра растёт почти линейно и на десяти тысячах вершин в Python быстрее в 16 раз. Поэтому Беллмана — Форда берут, только когда отрицательные рёбра действительно есть или нужен сам отрицательный цикл.
Частое ускорение — очередь: проверять рёбра только из вершин, чьё расстояние изменилось в прошлый раз. Этот вариант описал ещё Эдвард Мур в 1959 году; в олимпиадном программировании его знают как SPFA. На случайных графах он обычно быстрее, но худший случай остаётся O(V · E), и графы, на которых очередь работает медленно, строить умеют.
Где работает
Маршрутизация. В протоколе RIP каждый маршрутизатор знает только соседей и раз за разом сообщает им свои расстояния до всех сетей — это раунды Беллмана — Форда, разнесённые по разным машинам. RFC 1058 (1988) называет такие алгоритмы дистанционно-векторными и замечает, что их называют и именем Беллмана — Форда. Там же описана беда распределённой версии — «счёт до бесконечности»: когда сеть пропадает, соседи продолжают ссылаться друг на друга и медленно повышают расстояние. Поэтому в RIP бесконечность — это 16, а маршрутов длиннее 15 переходов не бывает.
Потенциалы. Алгоритм Джонсона один раз запускает Беллмана — Форда, чтобы подобрать каждой вершине число h(v), после которого все длины w(u, v) + h(u) − h(v) неотрицательны, и дальше считает кратчайшие пути Дейкстрой. Это тот же приём, что делает A* правильным, — приведённые длины.
Системы разностных ограничений. Расписание, где «работа B начинается не раньше чем через 3 дня после A» и «C — не позже чем через 5 дней после B», — это неравенства вида xv − xu ≤ c. Каждое — ребро u → v длины c, а неравенство треугольника для кратчайших расстояний ровно такое же. Решение системы — расстояния от добавленной вершины, связанной со всеми рёбрами длины 0, а если решения нет, Беллман — Форд находит отрицательный цикл — противоречивую цепочку требований.
Потоки минимальной стоимости. Поток можно улучшать, пока в остаточной сети есть цикл отрицательной стоимости, — его ищут тем же способом. Подробнее — в статье о потоке минимальной стоимости.
История
Алгоритм открывали несколько раз почти одновременно. Альфонсо Шимбел описал его в 1955 году, Лестер Форд — в 1956-м в отчёте корпорации RAND о теории сетевых потоков, Ричард Беллман — в 1958-м в заметке «On a routing problem», Эдвард Мур — в 1959-м, в той же работе о поиске пути в лабиринте, которую вспоминают и в статье о поиске в ширину. Поэтому алгоритм называют то Беллмана — Форда, то Беллмана — Форда — Мура. Беллман вывел его из своего принципа оптимальности — той самой динамики: кратчайший путь до вершины складывается из кратчайшего пути до соседа и одного ребра.
Задачи
В первой задаче нужно найти выгодный круг обменов или доказать, что его нет, и проверка точная: среди тестов курсы одного Нацбанка, где выгоды нет, а программа без запаса её находит. Во второй число обменов ограничено, и раунд без копии массива тихо делает лишние.
Выгодный круг обменов Не больше k обменовДанные: Курсы валют на 9 октября 2026: Национальный банк (курсы тенге) и ЕЦБ через Frankfurter