Маршрутизация: кратчайший путь по дорогам

Урок показывает, что построение маршрута — это поиск кратчайшего пути в графе, и реализует алгоритм Дейкстры на стандартной библиотеке.

Дорожная сеть моделируется графом: перекрёстки — вершины, участки дорог — рёбра с весом (длиной или временем проезда). Маршрут — это путь минимального суммарного веса.

Когда навигатор строит путь из точки А в точку Б, он не «смотрит на карту» — он решает классическую задачу теории графов. Это прямая связь ГИС с алгоритмами: дороги превращаются в граф, и дальше работает математика поиска кратчайшего пути. Вес ребра может быть длиной в метрах, временем с учётом пробок или даже «стоимостью» (платные дороги) — алгоритм один и тот же.

Дорога как граф

       4
   A ----- B
   |       |
  1|       |1
   |   2   |
   C ----- B (через C короче!)

   Путь A->B напрямую = 4
   Путь A->C->B = 1 + 2 = 3  (короче)

Хитрость в том, что самый прямой по карте путь не всегда самый короткий по сумме весов — объезд через C может оказаться быстрее. Алгоритм Дейкстры систематически находит истинный минимум.

Алгоритм Дейкстры

Идея: идём от старта, всегда выбирая ещё не обработанную вершину с наименьшим известным расстоянием, и «расслабляем» (обновляем) расстояния до её соседей. Очередь с приоритетом (модуль heapq) даёт нужную вершину быстро:

import heapq

# Граф дорог: вершина -> список (сосед, вес)
graph = {
    "A": [("B", 4), ("C", 1)],
    "C": [("B", 2), ("D", 5)],
    "B": [("D", 1)],
    "D": [],
}

def dijkstra(graph, start, goal):
    dist = {start: 0}
    prev = {}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if u == goal:
            break
        if d > dist.get(u, float("inf")):
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    # восстановить путь
    path = [goal]
    while path[-1] != start:
        path.append(prev[path[-1]])
    path.reverse()
    return dist[goal], path

cost, route = dijkstra(graph, "A", "D")
print(f"Длина пути: {cost}")
print("Маршрут:", " -> ".join(route))

Вывод:

Длина пути: 4
Маршрут: A -> C -> B -> D

Алгоритм нашёл путь $A \to C \to B \to D$ длиной $1 + 2 + 1 = 4$, а не прямой $A \to B \to D$ длиной $4 + 1 = 5$. Объезд оказался выгоднее — именно это и делает навигатор.

Как работает под капотом

Дейкстра гарантирует оптимум при неотрицательных весах (а расстояния и время всегда $\geq 0$). Его сложность с бинарной кучей — $O((V + E)\log V)$. На картах целой страны этого мало, поэтому навигаторы используют ускорения: A* добавляет эвристику «по прямой к цели» и режет перебор; промышленные движки (OSRM, GraphHopper) применяют предобработку (contraction hierarchies), отвечая за миллисекунды. Сам дорожный граф строят из данных OpenStreetMap: теги highway задают тип дороги, односторонность (oneway) делает рёбра направленными, а ограничения поворотов добавляют тонкости. В Python с этим работает библиотека networkx поверх графа из osmnx.

Частые ошибки

Игнорировать односторонние улицы. Если ребро ненаправленное, маршрут поедет против движения.
Брать длину вместо времени. Кратчайший по расстоянию путь через дворы бывает медленнее объезда по шоссе.
Применять Дейкстру с отрицательными весами. Она этого не допускает; для таких задач нужен Беллман-Форд.

От учебного графа к настоящим картам

Учебный граф из четырёх вершин и реальная дорожная сеть мегаполиса различаются на порядки, и именно эти различия рождают всю инженерию маршрутизации. Граф города это миллионы вершин и рёбер, и чистый Дейкстра, хоть и оптимальный, на каждый запрос обходит пол-карты. Поэтому навигаторы добавляют эвристику направления к цели (алгоритм A*), которая отсекает заведомо «не туда» ветви, и тяжёлую предобработку: contraction hierarchies заранее строят «скоростные ярусы» графа, благодаря которым маршрут через всю страну находится за миллисекунды. Понимание базового Дейкстры — фундамент, на котором все эти ускорения становятся осмысленными, а не магией.

Не менее важна семантика весов, потому что от неё зависит, какой маршрут вы получите. Вес ребра как длина даёт кратчайший путь, который может вести через дворы и грунтовки; вес как время с учётом скоростного режима даёт быстрый путь по магистралям; вес с пробками меняется каждые минуты и требует пересчёта на лету. Реальные графы ещё и направленные (односторонние улицы — рёбра в одну сторону) и хранят запреты поворотов, которые в простой модели «вершина-ребро» не выражаются и требуют расширения графа. Поэтому промышленная маршрутизация — это на 20% алгоритм и на 80% корректная модель дорожной сети из данных OpenStreetMap.

Итог

Маршрут — это кратчайший путь в графе дорог (вершины-перекрёстки, рёбра-улицы).
Алгоритм Дейкстры находит оптимум при неотрицательных весах.
Вес ребра — длина, время или стоимость; алгоритм один.
Реальные навигаторы ускоряют поиск через A* и предобработку графа.