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

Доцент Индийского технологического института Гандхинагара Манодж Гупта предложил усовершенствованный метод поиска кратчайших расстояний в графах. Работу он представил на 66-м симпозиуме FOCS 2025, посвящённом основам компьютерных наук. Эту информацию сообщает издание RuTab.net.

Речь идёт о задаче All-Pairs Shortest Paths (APSP): требуется найти кратчайшие маршруты между всеми парами вершин графа. В плотных сетях классические подходы требуют кубического времени — при удвоении числа точек объём расчётов растёт примерно восьмикратно. Подобные вычисления нужны картографическим сервисам, транспорту, коммуникациям, а также биологам, изучающим структуры от белков до нейронных связей.

В 1996 году Дор, Хальперин и Цвик (DHZ) обошли это препятствие с помощью приближённого метода. Для удалённых друг от друга точек он выдаёт оценку не более чем вдвое выше реального расстояния — так называемое 2-приближение. Истинный маршрут в 10 км такая оценка покажет в пределах от 10 до 20 км. Опорой служит небольшая выборка вершин-«ярлыков», по которым дистанция оценивается быстро.

На близких парах метод давал сбои: выбранные точки оказывались слишком далеко от прямого пути, и двукратный порог нарушался. Гарантия точности поэтому распространялась только на удалённые пары, и ограничение держалось почти три десятилетия. Гупта применил многоуровневое сэмплирование: сведения о сети раскладываются на несколько масштабов, а не хранятся в одном слое выборки. Это позволяет учитывать короткие маршруты, которые прежние схемы упускали, и снижает минимальное расстояние, где 2-приближение остаётся в силе, при сохранении общей вычислительной сложности.

В транспортных терминах разница выглядит так: DHZ надёжно оценивал длинные перегоны вроде Дели — Ченнаи, а новый подход сохраняет ту же точность на коротких отрезках, например между районами пригорода Мумбаи. Результат пока чисто теоретический и не обещает быстрых улучшений в коммерческих продуктах. Однако он укрепляет математическую базу алгоритмов для больших сетей — интернета, транспорта, социальных платформ и приложений искусственного интеллекта, — развивая влиятельную работу 1996 года.