Задача поиска кратчайших путей между всеми парами точек, известная как APSP, возникает далеко не только в навигации. В виде графов можно представить интернет, транспортные системы, социальные сети, взаимодействия белков и множество других сложных систем.
При большом количестве связей точное вычисление всех расстояний требует огромных ресурсов. Поэтому еще в 1996 году исследователи Дор, Хальперин и Цвик предложили быстрый приближенный алгоритм, способный оценивать расстояние с гарантией, что результат не превышает реальное значение более чем вдвое.
Метод хорошо работает для удаленных друг от друга точек, но заметно хуже справляется с близкими. Причина заключается в использовании ограниченного набора опорных вершин: на длинном маршруте подходящая точка с высокой вероятностью окажется поблизости, тогда как короткий путь может полностью пройти мимо них.
Манодж Гупта из Индийского технологического института в Гандинагаре предложил использовать несколько уровней таких опорных точек, соответствующих разным масштабам графа. Благодаря этому алгоритм сохраняет двукратную гарантию приближения для значительно большего числа коротких маршрутов, не ухудшая общую временную сложность вычислений.
Разработка была представлена на конференции FOCS 2025 и пока остается прежде всего теоретическим результатом. Однако подобные алгоритмы лежат в основе обработки огромных сетей, поэтому улучшение почти 30-летнего метода потенциально может пригодиться в телекоммуникациях, транспортных системах, биоинформатике и других областях, где важнее быстро получить достаточно точный ответ, чем долго вычислять идеальный.
Читать TechDigest в Google
