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

Алгоритм Дейкстры: как найти самый короткий и самый дешёвый путь

Время чтения: 7 мин 25 сек
09 ноября 2026 Просмотров: 15

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

Алгоритм Дейкстры: как найти самый короткий и самый дешёвый путь

Рис. 1. Закрепить ближайшую точку и пересчитать соседей: схема по ГОСТ 19.701

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

В какой-то момент разделились. Поднялся наверх, а смешливые мужчины понуро махали с соседней возвышенности: вроде рядом, но через ущелье не перелететь – чай не птицы.

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

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

Какой путь считать коротким?

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

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

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

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

Эдсгер Дейкстра придумал алгоритм в 1956 году за двадцать минут на террасе амстердамского кафе, без карандаша и бумаги, а опубликовал через три года.

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

Сервисная компания «Кедр» отправляет бригаду с базы на насосную клиента. По пути – склад, центр, развязка и цех, у каждого участка – время в пути в минутах.

image html

Рис. 2. Шесть точек сети и самый быстрый маршрут

Путь через центр выглядит коротким: два участка и 35 минут. Алгоритм закрепляет склад, центр, развязку и цех и находит путь в четыре участка за 26 минут – девять минут экономии.

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

image html

Рис. 3. Шесть шагов алгоритма Дейкстры для бригады «Кедра»

Почему опыт бывает точнее расчёта?

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

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

Как найти самый дешёвый путь денег?

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

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

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

image html

Рис. 4. Пример: длинная цепочка за 18% и обход за 9%

Где расчёт обманывает?

В 2016 году создал «теорию абсолютной верификации» на основе частотного анализа отказов в выдаче кредитов. Всё казалось логичным, но молодой андеррайтер нашёл более короткий путь, воспользовавшись «ошибкой выжившего».

Алгоритм найдёт минимум на любой карте, даже неверной. Если цены посчитаны по неполной выборке, лучший маршрут окажется лучшим только на бумаге.

Что делать, если сеть огромна?

Алгоритм A* – способ ускорить Дейкстру подсказкой: к пройденному пути добавляют оценку остатка – расстояние по прямой до цели. Поиск тянется к цели и не расползается по сети.

A* предложили Питер Харт, Нильс Нильссон и Бертрам Рафаэл в 1968 году, когда учили робота Shakey объезжать препятствия. Главное: догадка не должна завышать длину до финиша, иначе результат перестанет быть кратчайшим.

Направление без карты – уже не A*, а жадный шаг к цели. Именно так можно оказаться на соседней возвышенности: вершина рядом, а ущелья в оценке нет.

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

Модель: в районе из 10 × 10 перекрёстков одних маршрутов, которые ни разу не поворачивают назад, от угла до угла – 48’620. Перебор по 10 секунд на маршрут займёт 135 часов.

Пошаговый метод проверит каждый из 180 участков с двух сторон: 360 проверок – ровно час. Компьютер решает такую сеть за миллисекунды, а целый город – в мгновение ока.

Когда уместен алгоритм Дейкстры?

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

Если бывают минусы – скидки, возвраты, бонусы, – решённая точка может подешеветь позже, уже после закрепления. Алгоритм этого не заметит и уверенно выдаст неверный путь, а руководитель примет его за лучший.

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

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

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

Граф с ценами участков показывает сеть и выбранный путь сразу. Его любят руководители и диспетчеры: видно, где обход дешевле прямой дороги и во что на самом деле обходится привычный маршрут бригады.

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

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

Лучшая нотация для кратчайшего пути – граф с ценами участков: 21 балл против 19 у таблицы проходов и 16 у ГОСТ. Руководитель за минуту видит маршрут и отвергнутые обходы. Вес вопроса о руководителе удвоен: сборник написан для него.

image html

Рис. 5. Оценка трёх нотаций: 16, 21 и 19 баллов

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

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

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

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

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

  • кратчайший путь – маршрут с наименьшей суммой цен участков
  • алгоритм Дейкстры закрепляет ближайшую точку и пересчитывает соседей
  • путь хорош настолько, насколько верны цены участков
  • A* ускоряет поиск подсказкой, но не заменяет карту
  • кратчайший путь лучше всего рисовать графом с ценами участков.