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

Рис. 1. Схема по ГОСТ 19.701: повторные проходы и финальная проверка
Когда впервые решил сделать кругосветное путешествие, с удивлением узнал, что серия билетов «в один конец по экватору» стоит дешевле половины от каждого сегмента с возвратом.
Позже понял, почему именно длинные пути чаще оказываются выгоднее. Скидка на сквозной маршрут работает как участок с минусом: путь удлиняется, а сумма падает.
Короткий ответ: алгоритм Беллмана – Форда находит самый выгодный путь, даже если у части переходов цена отрицательная, и замечает петли, по которым «выгода» растёт бесконечно.
Рисовать его руководителю удобнее всего на языке ДРАКОН: шампур сверху вниз, ветки вправо и ни одного пересечения линий.
Почему длинное бывает дешевле?
Участок с минусом – способ учесть в цене пути скидку, бонус, зачёт или доход: пройти его выгоднее, чем не проходить. Поэтому обходной маршрут выигрывает у прямого.
Как устроен поиск?
Алгоритм Беллмана – Форда – способ найти выгодные пути от начальной точки, когда цены бывают отрицательными. Он делает (N – 1) проходов по всем участкам и на каждом уменьшает оценку «куда», если путь через «откуда» дешевле.
Ничего не закрепляют заранее: минус далеко впереди может снизить стоимость пункта, который Дейкстра уже счёл решённым. Контрольная итерация ловит петли с минусом: если цифры продолжают снижаться, выгода бесконечна.
Первым метод предложил Альфонсо Шимбел в 1955 году, а имя он получил по Лестеру Форду и Ричарду Беллману, опубликовавшим его в 1956 и 1958 годах.
Как это выглядит на деле?
Сервисная компания «Кедр» везёт насос с базы на объект. Крюк через завод партнёра длиннее, но там берут попутный груз: доход перекрывает дорогу, и участок от завода до склада стоит минус 7 тысяч рублей за каждый рейс.

Рис. 2. Пять точек сети и одна отрицательная цена
Дейкстра закрепляет склад по цене 4 тысячи и выдаёт путь за 11. Беллман – Форд пересчитывает склад через завод до 1 тысячи и находит путь за 8 – дешевле на 3 тысячи.
Таблица проходов – способ показать, как оценки уменьшаются от прохода к проходу. При неудачном порядке участков хватает четырёх проходов, а пятый ничего не меняет.

Рис. 3. Цена пути сходится к 8 тысячам рублей
Почему скидка бывает дороже?
Согласился купить бумагу у знакомых в большом объёме по сниженной цене. Радость была недолгой: при формальном соответствии по всем параметрам эту А4 не хотели захватывать механизмы протяжки принтеров и ксероксов.
Расходы на устранение замятий многократно превысили ожидаемую экономию.
Приобрёл для клиник дорогостоящие фильтры: один на кухню, чтобы чай и кофе для сотрудников и гостей стали вкуснее, второй – чтобы заливать очищенную воду в стерилизатор.
Оказалось, что кроме плюсов заготовлен серьёзнейший минус: приученные коллеги не хотели отказываться от хорошего, а расходники дорожали с ростом курса евро.
Сниженная цена – только первый шаг, а за ним следуют затратные звенья: замятия, картриджи фильтров, валюта. Итог пути решает сумма до конца, а не начало.
Что такое бесконечная выгода?
Разрабатывал систему лояльности для европейского магазина посуды, попросили «невер ендинг стори». Вспомнил алгоритмы и придумал модель: клиент уверяет домашних в выгодности каждой сделки, но не может остановиться, пока не выкупит «весь ассортимент».
Это круг с минусом: каждый шаг кажется удачным, и сумма по кругу уменьшается без конца. Беллман – Форд находит его проверочным проходом – полезно маркетологу и покупателю.

Рис. 4. Пример: петля из четырёх товаров и «экономия» 10 евро за оборот
Сколько стоит расчёт?
Алгоритм делает до (N – 1) проходов по всем участкам. Модель: для сети из 1’000 точек и 5’000 участков – до 5 миллионов проверок против примерно 50 тысяч у Дейкстры с кучей.
Для компьютера это доли секунды, поэтому платить скоростью за правильность на сетях со скидками стоит. На сетях без минусов быстрее метод из прошлой статьи.
Когда уместен алгоритм Беллмана – Форда?
Там, где бывают минусы: скидки, бонусы, зачёты, попутные доходы. И там, где важно проверить, нет ли круга бесконечной «выгоды»: в программах лояльности и взаимозачётах.
В следующей статье сборника – алгоритмы Краскала и Прима: как связать все объекты самой дешёвой сетью дорог, кабелей или труб.
Какими нотациями рисовать путь с минусами?
ГОСТ 19.701 точно передаёт оба цикла и проверку, его ценят разработчики и аудиторы.
ДРАКОН – способ рисовать алгоритм шампуром: главный маршрут сверху вниз, ветки – вправо, линии не пересекаются. Его предпочитают авторы регламентов, где ошибка дорога.

Рис. 5. Тот же алгоритм на языке, созданном для «Бурана»
Таблицей проходов пользуются аналитики и ИИ: каждую цифру можно проверить.
Какая нотация лучше?
Лучшая нотация для путей с минусами – ДРАКОН: 20 баллов против 18 у таблицы проходов и 16 у ГОСТ. Руководитель за минуту видит оба цикла и проверку, линии не путаются. Вес вопроса о руководителе удвоен: сборник написан для него.

Рис. 6. Оценка трёх нотаций: 16, 20 и 18 баллов
Таблица проходов отстала на два балла и нужна при разборе цифр. ГОСТ остаётся для разработчиков, которым привычнее стандарт.
Что сделать руководителю?
Хватит четырёх шагов:
- Найдите в сети участки с минусом: скидки, бонусы, зачёты и попутные доходы.
- Допишите расходы, которые идут следом: обслуживание, материалы, курс, простои.
- Считайте путь алгоритмом Беллмана – Форда, а не по первому выгодному шагу.
- Проверьте сеть на круги с минусом, прежде чем запускать бонусы и взаимозачёты.
Что запомнить?
- участок с минусом – скидка, бонус или доход, из-за которого длинный путь дешевле
- Беллман – Форд делает (N – 1) проходов и не закрепляет точки заранее
- контрольная итерация находит круги бесконечной «выгоды»
- выгоду пути считают до конца, вместе с расходами после скидки
- путь с минусами лучше всего рисовать на языке ДРАКОН.