Индийский учёный улучшил алгоритм поиска кратчайших путей без потери скорости

Почти 30 лет специалисты бились над этой задачей, и теперь она наконец сдвинулась с мёртвой точки. Маной Гупта из Индийского технологического института Гандинагара предложил улучшение алгоритма поиска кратчайших путей между всеми парами вершин графа. Работа опубликована на симпозиуме FOCS 2025. Главное её достижение: гарантия точности теперь распространяется и на близко расположенные узлы.

Где старый метод давал сбой

В 1996 году Дор, Хальперин и Цвик предложили эффективный способ: выбрать небольшой набор опорных точек-«ориентиров» и через них оценивать длинные маршруты, например между Дели и Ченнаи, не перебирая все возможные пути. Для дальних точек это работало хорошо. Для близких же ориентиры часто оказывались далеко от кратчайшего соединения. Пример из сообщений: между двумя районами Мумбаи алгоритм мог выдать путь из пяти рёбер вместо реальных двух, то есть нарушал гарантию «не более чем в 2 раза».

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

Почему задача важна за пределами карт

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

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

По материалам: [noleech]iXBT[/noleech]