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