Парадокс кратчайшего пути
Откройте любой навигатор. Постройте маршрут от дома до работы. Скорее всего, вам предложат три варианта: «быстрый», «короткий» и «пеший». Но вот загадка: «короткий» часто оказывается медленнее «быстрого», а «быстрый» — длиннее в километрах. Как так? Дело в том, что компьютер не знает, что такое «дорога». Он знает только граф — набор точек (перекрёстков) и линий (улиц) между ними. И когда вы просите «кратчайший путь», компьютер понимает это буквально: сумма длин линий.
Как улицы превращаются в математический граф
Перед тем как искать маршрут, ГИС преобразует карту в структуру данных. Это называется построением сетевого графа.
Шаг 1. Узлы — это перекрёстки
Каждый перекрёсток становится точкой — узлом графа. Не каждый изгиб улицы, а именно место, где можно свернуть. Тупик — узел. Развязка магистрали — узел. Выезд со двора на улицу — тоже узел.
Шаг 2. Рёбра — это участки улиц
Отрезок между двумя узлами — ребро. У ребра есть атрибуты:
- Длина — в метрах, по геометрии линии
- Направление — одностороннее или двустороннее
- Тип дороги — магистраль, проспект, переулок, грунтовка
- Скорость — максимально разрешённая или средняя фактическая
Шаг 3. Топология — связи между рёбрами
Важнейший момент: какие повороты возможны. С узла А можно попасть в узел Б напрямую? Или нужно объехать квартал? Здесь работают манёвры (turn restrictions) — запреты на повороты, развороты, съезды.
Алгоритм Дейкстры: как искать путь в лабиринте
В 1956 году голландский учёный Эдсгер Дейкстра придумал алгоритм, который до сих пор лежит в основе большинства навигаторов. Принцип прост, как наводнение.
Аналогия с водой
Представьте, что вы стоите в точке А и открываете кран. Вода течёт по улицам со скоростью, обратной «стоимости» проезда. Сначала заполняются ближайшие перекрёстки, потом следующие, и так далее. Как только вода достигла точки Б — путь найден. Причём найден оптимальный: вода дошла самым коротким (или быстрым) путём.
Пошагово:
- Инициализация. Точке А присваиваем стоимость 0. Всем остальным — бесконечность.
- Выбор текущего узла. Берём узел с наименьшей известной стоимостью (сначала это А).
- Обход соседей. Для каждого соседа считаем: стоимость текущего узла + стоимость ребра. Если получилось меньше текущей стоимости соседа — обновляем.
- Помечаем текущий узел как посещённый. Больше не возвращаемся к нему.
- Повторяем шаги 2-4, пока не достигнем точки Б или не закончатся узлы.
Почему это работает: алгоритм всегда выбирает ближайшую непосещённую точку. Значит, когда мы дошли до цели, нет другого пути, который мог бы быть короче — иначе мы бы пошли туда раньше.
В классическом варианте Дейкстра минимизирует сумму длин рёбер. Но в реальной жизни мы хотим минимизировать время. Как это исправить? Простой трюк: взвешивание по времени — вместо метров используем секунды. Стоимость ребра = длина / скорость. Теперь алгоритм ищет не короткий, а быстрый путь.
Почему навигатор ведёт «через дворы»
Классический случай: стоите в центре, ехать 2 километра по прямой. Навигатор выстраивает маршрут через серию дворов, подворотен и переулков. Почему? Самая распространенная причина топология без контекста. Для алгоритма дворовой проезд и магистраль — просто рёбра с длиной и скоростью. Если дворовой проезд короче, а ограничение скорости не задано (или задано неверно), алгоритм посчитает его выгодным. Умные навигаторы используют иерархический поиск: сначала ищут путь по магистралям между районами, потом — внутри районов. Если иерархия не настроена, алгоритм буквально «ползёт» по всему графу, находя локально оптимальные, но глобально странные решения.
Построение маршрута поэтапно: что происходит за секунды
Когда вы нажимаете «Построить маршрут», происходит следующее:
Этап 1. Привязка точек к графу (1-2 мс)
Ваше местоположение и точка назначения — координаты на земле. Их нужно «привязать» к ближайшим узлам графа. Но не просто к ближайшим: нужно учесть, с какой стороны улицы вы стоите, в каком направлении смотрите, есть ли пешеходный переход.
Этап 2. Поиск пути (10-100 мс для A*, до секунды для Дейкстры)
Запускается алгоритм на подграфе: обычно не на всём городе, а на ограниченной зоне «вокруг» прямой линии между точками. Для дальних поездок используется иерархия: сначала магистрали между районами, потом — дороги внутри районов.
Этап 3. Постобработка (5-20 мс)
Найденный путь — это цепочка рёбер. Её нужно превратить в понятные инструкции: «поверните налево», «продолжайте 2 километра», «съезд на кольцевой». Алгоритм ищет ориентиры, подписывает названия улиц, оценивает время прибытия.
Этап 4. Рендеринг (10-50 мс)
Маршрут рисуется на карте: выделение цветом, стрелки, номера поворотов. Подготавливаются данные для голосовых подсказок.
Всё это — за доли секунды. Но за этой скоростью — гигантские предвычисления: граф города построен заранее, индексы пространственные созданы, скорости профилированы по времени суток.
Не всегда доверяйте «короткому» пути. Он может вести через улицы или переулки, где вы потеряете время на поворотах и светофорах. «Быстрый» обычно надёжнее. Понимание, как работает алгоритм, помогает критически оценивать его советы. И иногда — игнорировать их, выбирая свой путь.