Как навигатор находит кратчайший путь: алгоритм Дейкстры на пальцах

Ты вбиваешь в навигатор адрес, и через секунду на экране загорается синяя линия — самый быстрый путь из точки А в точку Б. Но дорог-то тысячи, перекрёстков ещё больше, а вариантов проехать — вообще астрономическое число. Как телефон умудряется перебрать всё это и не зависнуть? Секрет — в изящном алгоритме, который придумал голландец Эдсгер Дейкстра в 1956 году, размышляя за чашкой кофе.

Сначала превратим город в точки и линии

Чтобы компьютер мог искать путь, реальную карту нужно перевести на его язык. Этот язык называется граф. Звучит страшно, но идея простейшая: каждый перекрёсток — это точка (математики говорят «вершина»), а каждая улица между двумя перекрёстками — это линия между точками (её называют «ребро»).

Самое важное — у каждой линии есть вес. Вес — это «цена» проезда по улице. Чаще всего это время в пути или расстояние. Короткая улочка без пробок весит мало, длинный проспект с десятью светофорами — много. Задача навигатора звучит теперь так: найти цепочку линий от старта до финиша, у которой сумма весов самая маленькая.

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

Главная идея: жадничать, но с умом

Вот тут на сцену выходит сам алгоритм Дейкстры. Его логика похожа на то, как растекается вода или расходится круг волн от брошенного в пруд камня. Алгоритм не пытается сразу угадать весь маршрут. Он действует по шагам, аккуратно расползаясь от старта во все стороны.

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

• Из всех ещё не обработанных точек выбираем ту, до которой цена сейчас самая маленькая.
• Смотрим на всех её соседей и проверяем: а не получится ли добраться до них дешевле, если идти через эту точку?
• Если да — обновляем сосе́ду его число на более выгодное.
• Точку, которую только что разобрали, помечаем как «готово» и больше к ней не возвращаемся.

И так раз за разом, пока не доберёмся до финиша. Ключевой фокус — в первом пункте. Алгоритм всегда хватается за самую дешёвую из доступных точек. Это называется жадным выбором.

Аналогия: вода, которая ищет выход

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

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

Именно поэтому алгоритм можно смело останавливать, как только разобрана точка-финиш: раз мы дошли до неё по самому дешёвому из доступных вариантов, ничего лучше уже не появится. И именно поэтому Дейкстра предъявляет одно требование — веса не должны быть отрицательными. «Отрицательная улица», которая возвращала бы тебе время, сломала бы всю логику воды: она вдруг могла бы прибежать назад и удешевить уже «залитый» перекрёсток. К счастью, в реальных картах время и расстояние отрицательными не бывают.

Почему это не тормозит на огромных картах

Казалось бы, перекрёстков в большом городе сотни тысяч, а дорог между ними ещё больше. Почему телефон не думает над маршрутом полчаса?

Хитрость в том, что Дейкстра не перебирает все возможные маршруты — таких действительно было бы астрономически много. Он обрабатывает каждый перекрёсток ровно один раз и для каждого лишь быстро обновляет соседей. Чтобы мгновенно находить самую дешёвую необработанную точку, используют специальную структуру — очередь с приоритетом (её ещё называют «куча»). Она работает как умная очередь в поликлинике, где вперёд всегда пропускают того, кому нужнее, и не приходится каждый раз перебирать всех пациентов.

Благодаря этому время работы растёт не катастрофически, а очень умеренно — примерно пропорционально числу дорог, умноженному на логарифм числа перекрёстков. На практике это означает, что даже карта целого города обрабатывается за доли секунды. А в настоящих навигаторах поверх Дейкстры навешивают ещё ускорители: алгоритм A*, который подсказывает «иди в сторону цели», и предварительно посчитанные «магистральные» связи между районами.

Так что в следующий раз, когда навигатор за мгновение нарисует тебе путь через полгорода, вспомни: внутри тихо разливается математическая «вода», придуманная одним человеком почти семьдесят лет назад. Та самая идея сегодня прокладывает маршруты пакетам данных в интернете, героям в видеоиграх и роботам-пылесосам по твоей квартире. Неплохо для пары минут размышлений за кофе.