Автострадная размерность и доказуемо эффективные алгоритмы нахождения кратчайших путей

Задача о нахождении оптимального маршрута породила множество эвристических алгоритмов, отвечающих на запросы на континентальных картах с десятками миллионов перекрестков в реальном времени с весьма скромными затратами по памяти.

Мы приводим первый теоретический анализ таких алгоритмов на нетривиальном классе графов. С этой целью мы вводим понятие автострадной размерности (highway dimension). Рассматриваемый анализ применим к графам с низкой размерностью и даёт единообразное объяснение эффективности нескольких, на первый взгляд различных, алгоритмов.