Задача, не поддававшаяся 30 лет, решена: алгоритм поиска кратчайших путей стал точнее без потери скорости ixbt.com

Маной Гупта (Manoj Gupta), доцент Индийского технологического института Гандинагара, представил улучшение алгоритма поиска кратчайших путей между всеми парами вершин в графе (All-Pairs Shortest Paths, APSP). Результат, опубликованный на симпозиуме FOCS 2025, впервые с 1996 года сдвигает границу, за которой гарантируется 2-приближение — то есть оценка расстояния не более чем вдвое превышает реальное, но теперь и для гораздо более близких друг к другу узлов сети.

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

Источник изображения: сгенерировано Muse

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

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

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