2026.02.12

Новый алгоритм поиска кратчайших путей: успех в теории, но не в практике

Новый алгоритм поиска кратчайших путей в сетевых системах привлек внимание исследователей, однако вряд ли он сможет заменить метод Дейкстры в практических маршрутизаторах. Исследование утверждает, что новый подход превосходит алгоритм, предложенный Эдсгером Дейкстрой в 1959 году, который, в свою очередь, лег в основу популярных маршрутизационных протоколов OSPF и IS-IS. Новый алгоритм представляет собой кардинально иной метод, который обходит «барьер сортировки» и улучшает производительность за счет упрощенных операций. Хотя теоретическая корректность нового метода проверена, его практическая значимость вызывается сомнениями. Алгоритм Дейкстры функционирует с нагрузкой n log n + m, в то время как новый показывает производительность m log2/3 n при увеличении n. Однако для многих реальных задач справедливость этих результатов может зависеть от масштабируемости и конкретных условий. Кроме того, время расчета — лишь часть общей производительности. Важную роль играют также скорость обнаружения сбоев и скорость обработки состояния сети. Поэтому, несмотря на новые исследования, метод Дейкстра останется актуальным благодаря своей простоте и понятности для реализации.