Публикация Школы траблшутеров

Алгоритм Беллмана – Форда: как найти выгодный путь со скидками и бонусами

Время чтения: 6 мин 25 сек
10 ноября 2026 Просмотров: 11

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

Алгоритм Беллмана – Форда: как найти выгодный путь со скидками и бонусами

Рис. 1. Схема по ГОСТ 19.701: повторные проходы и финальная проверка

Когда впервые решил сделать кругосветное путешествие, с удивлением узнал, что серия билетов «в один конец по экватору» стоит дешевле половины от каждого сегмента с возвратом.

Позже понял, почему именно длинные пути чаще оказываются выгоднее. Скидка на сквозной маршрут работает как участок с минусом: путь удлиняется, а сумма падает.

Короткий ответ: алгоритм Беллмана – Форда находит самый выгодный путь, даже если у части переходов цена отрицательная, и замечает петли, по которым «выгода» растёт бесконечно.

Рисовать его руководителю удобнее всего на языке ДРАКОН: шампур сверху вниз, ветки вправо и ни одного пересечения линий.

Почему длинное бывает дешевле?

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

Как устроен поиск?

Алгоритм Беллмана – Форда – способ найти выгодные пути от начальной точки, когда цены бывают отрицательными. Он делает (N – 1) проходов по всем участкам и на каждом уменьшает оценку «куда», если путь через «откуда» дешевле.

Ничего не закрепляют заранее: минус далеко впереди может снизить стоимость пункта, который Дейкстра уже счёл решённым. Контрольная итерация ловит петли с минусом: если цифры продолжают снижаться, выгода бесконечна.

Первым метод предложил Альфонсо Шимбел в 1955 году, а имя он получил по Лестеру Форду и Ричарду Беллману, опубликовавшим его в 1956 и 1958 годах.

Как это выглядит на деле?

Сервисная компания «Кедр» везёт насос с базы на объект. Крюк через завод партнёра длиннее, но там берут попутный груз: доход перекрывает дорогу, и участок от завода до склада стоит минус 7 тысяч рублей за каждый рейс.

image html

Рис. 2. Пять точек сети и одна отрицательная цена

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

Таблица проходов – способ показать, как оценки уменьшаются от прохода к проходу. При неудачном порядке участков хватает четырёх проходов, а пятый ничего не меняет.

image html

Рис. 3. Цена пути сходится к 8 тысячам рублей

Почему скидка бывает дороже?

Согласился купить бумагу у знакомых в большом объёме по сниженной цене. Радость была недолгой: при формальном соответствии по всем параметрам эту А4 не хотели захватывать механизмы протяжки принтеров и ксероксов.

Расходы на устранение замятий многократно превысили ожидаемую экономию.

Приобрёл для клиник дорогостоящие фильтры: один на кухню, чтобы чай и кофе для сотрудников и гостей стали вкуснее, второй – чтобы заливать очищенную воду в стерилизатор.

Оказалось, что кроме плюсов заготовлен серьёзнейший минус: приученные коллеги не хотели отказываться от хорошего, а расходники дорожали с ростом курса евро.

Сниженная цена – только первый шаг, а за ним следуют затратные звенья: замятия, картриджи фильтров, валюта. Итог пути решает сумма до конца, а не начало.

Что такое бесконечная выгода?

Разрабатывал систему лояльности для европейского магазина посуды, попросили «невер ендинг стори». Вспомнил алгоритмы и придумал модель: клиент уверяет домашних в выгодности каждой сделки, но не может остановиться, пока не выкупит «весь ассортимент».

Это круг с минусом: каждый шаг кажется удачным, и сумма по кругу уменьшается без конца. Беллман – Форд находит его проверочным проходом – полезно маркетологу и покупателю.

image html

Рис. 4. Пример: петля из четырёх товаров и «экономия» 10 евро за оборот

Сколько стоит расчёт?

Алгоритм делает до (N – 1) проходов по всем участкам. Модель: для сети из 1’000 точек и 5’000 участков – до 5 миллионов проверок против примерно 50 тысяч у Дейкстры с кучей.

Для компьютера это доли секунды, поэтому платить скоростью за правильность на сетях со скидками стоит. На сетях без минусов быстрее метод из прошлой статьи.

Когда уместен алгоритм Беллмана – Форда?

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

В следующей статье сборника – алгоритмы Краскала и Прима: как связать все объекты самой дешёвой сетью дорог, кабелей или труб.

Какими нотациями рисовать путь с минусами?

ГОСТ 19.701 точно передаёт оба цикла и проверку, его ценят разработчики и аудиторы.

ДРАКОН – способ рисовать алгоритм шампуром: главный маршрут сверху вниз, ветки – вправо, линии не пересекаются. Его предпочитают авторы регламентов, где ошибка дорога.

image html

Рис. 5. Тот же алгоритм на языке, созданном для «Бурана»

Таблицей проходов пользуются аналитики и ИИ: каждую цифру можно проверить.

Какая нотация лучше?

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

image html

Рис. 6. Оценка трёх нотаций: 16, 20 и 18 баллов

Таблица проходов отстала на два балла и нужна при разборе цифр. ГОСТ остаётся для разработчиков, которым привычнее стандарт.

Что сделать руководителю?

Хватит четырёх шагов:

  1. Найдите в сети участки с минусом: скидки, бонусы, зачёты и попутные доходы.
  2. Допишите расходы, которые идут следом: обслуживание, материалы, курс, простои.
  3. Считайте путь алгоритмом Беллмана – Форда, а не по первому выгодному шагу.
  4. Проверьте сеть на круги с минусом, прежде чем запускать бонусы и взаимозачёты.

Что запомнить?

  • участок с минусом – скидка, бонус или доход, из-за которого длинный путь дешевле
  • Беллман – Форд делает (N – 1) проходов и не закрепляет точки заранее
  • контрольная итерация находит круги бесконечной «выгоды»
  • выгоду пути считают до конца, вместе с расходами после скидки
  • путь с минусами лучше всего рисовать на языке ДРАКОН.