Ежедневно навигационные приложения вроде Google Maps прокладывают кратчайший маршрут между двумя точками. Для этого сложные алгоритмы анализируют сети дорог и перекрёстков и подбирают эффективные пути. Однако задача заметно усложняется, если компьютеру нужно рассчитать кратчайшее расстояние сразу для каждой пары точек в огромной сети.
Подобные расчёты востребованы не только в картографии. Они важны для транспортных систем, сетей связи и даже биологических структур — белков, нейронов и других взаимосвязанных элементов. Чем крупнее сеть, тем труднее определить кратчайшие маршруты между всеми её точками. В информатике эта задача известна как All-Pairs Shortest Paths (APSP, поиск кратчайших путей между всеми парами вершин). В её рамках граф представляет собой набор точек (вершин), соединённых связями (рёбрами): это могут быть города, компьютеры, станции метро или органы, а связи — шоссе, кабели, железнодорожные линии или кровеносные сосуды.
Точный расчёт кратчайших расстояний в масштабной сети требует больших вычислительных ресурсов и памяти. В плотно связанных сетях некоторые традиционные методы работают за так называемое кубическое время: при удвоении числа точек объём вычислений возрастает примерно в восемь раз. Поскольку нагрузка растёт гораздо быстрее самой сети, специалисты десятилетиями ищут более эффективные подходы. Одно из перспективных решений — приближённые алгоритмы, которые дают оценки вместо точных значений: они позволяют получать достаточно точные расстояния при резком сокращении вычислений.
Важный шаг был сделан в 1996 году, когда исследователи Дор, Хальперин и Цвик (DHZ) предложили метод, оценивающий расстояние не более чем вдвое больше реального для достаточно удалённых точек и работающий почти за оптимальное время. Такую точность называют «2-приближением»: если кратчайший маршрут между двумя точками составляет 10 километров, оценка должна попасть в диапазон от 10 до 20 километров. Вместо перебора всех возможных маршрутов подход DHZ опирается на небольшую выборку точек сети, которые служат своеобразными «ярлыками» и помогают быстрее оценивать расстояния.
Метод хорошо работает, когда сравниваемые точки далеко друг от друга. Например, на маршруте между Дели и Ченнаи алгоритм часто находит выборочную точку рядом с кратчайшим путём и укладывается в обещанный предел. Но для близких точек та же стратегия менее надёжна: при расчёте пути между двумя районами пригорода Мумбаи выборочные точки могут оказаться слишком далеко от прямого соединения, и алгоритм оценит маршрут как значительно более длинный. Две точки могут быть связаны путём всего из двух рёбер, а выборочный маршрут — из пяти, и тогда результат нарушает гарантию «не более чем вдвое». Из-за этого исходная математическая гарантия действовала только для достаточно удалённых точек, и почти три десятилетия это оставалось ограничением.
Теперь доцент Индийского технологического института Гандинагара Манодж Гупта представил доработку, которая распространяет гарантию точности и на гораздо более близкие точки. Исследование было представлено на 66-м ежегодном симпозиуме по основам компьютерных наук (FOCS 2025) в работе «Improved 2-Approximate Shortest Paths for close vertex pairs» («Улучшенные 2-приближённые кратчайшие пути для близких пар вершин»). Улучшенный алгоритм сохраняет общее время работы прежнего подхода, но расширяет диапазон расстояний, для которых действует надёжная оценка. Прорыв связан с переосмыслением выборки точек: вместо одного набора представительных точек применяется многоуровневая стратегия, которая организует данные о сети на нескольких масштабах. Анализ связей на разных уровнях позволяет учитывать короткие маршруты, которые прежние методы могли пропускать, и снижает минимальное расстояние, при котором выполняется гарантия 2-приближения, не увеличивая вычислительную сложность алгоритма.
Масштабные сети лежат в основе современных технологий: интернет-инфраструктуры, транспорта, социальных платформ и систем искусственного интеллекта. Во многих случаях получить точное расстояние менее важно, чем быстро выдать надёжную оценку, а при огромном числе связей умение балансировать между точностью и скоростью особенно ценно. Работа Гупты, о которой сообщает ScienceDaily, укрепляет математические основы алгоритмов для таких задач. Хотя результаты носят теоретический характер и не означают немедленного улучшения конкретных коммерческих систем, они предлагают более совершенный подход к расчёту расстояний в больших сетях. Исследование также показывает, как структуру сети можно понять через тщательно отобранные локальные связи. Прогресс в теоретической информатике часто достигается постепенными уточнениями, и развитие влиятельного результата 1996 года — значимый шаг: расширив давнюю гарантию точности без роста времени работы, новый алгоритм выходит за важную математическую границу и усиливает методы, лежащие в основе сложных связанных систем.