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

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

Вехой стал 1996 год, когда исследователи Дор, Халперин и Цвик предложили подход, позволяющий получать оценки расстояний вдвое больше фактического на точках, удалённых друг от друга, сохраняя почти оптимальное время работы. Такой уровень точности называют 2‑аппроксимацией: например, путь длиной 10 км может оцениваться в диапазоне от 10 до 20 км. Именно этот принцип заложил основу последующих попыток расширить масштабируемость метода.

Теперь доктор Манодж Гупта,Associate Professor Индийского технического института Гандхинагара, представил уточнение метода, которое распространяет гарантию точности на пары точек, находящиеся гораздо ближе друг к другу, чем позволяло предшествующим методам. Подробности Гупты были представлены на 66-м ежегодном симпозиуме Foundations of Computer Science (FOCS 2025) в работе под названием «Improved 2-Approximate Shortest Paths for close vertex pairs».

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

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

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