Наука 1 ноября 2026, 22:56 МСК

Учёный расширил гарантии точности алгоритма поиска кратчайших путей

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

Работа доцента Индийского технологического института Гандинагара представлена на FOCS 2025 и развивает метод Дора, Хальперина и Цвика 1996 года. Речь идёт о задаче поиска кратчайших путей между всеми парами вершин с 2-приближением: оценка расстояния не должна превышать истинное более чем вдвое.

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

• Работа представлена на FOCS 2025
• Гарантия 2-приближения расширена на более близкие вершины
• Вычислительная сложность метода не увеличилась