Новый алгоритм поиска путей в сетях: интерес, но не замена Дейкстре
Новый алгоритм поиска кратчайших путей в сетях привлек внимание научного сообщества, однако, вероятно, не сможет заменить классический метод Дейкстры, известный с 1959 года. Дейкстра лег в основу основных протоколов маршрутизации, таких как OSPF и IS-IS. Последний требует использования именно этого метода, что делается на протяжении десятилетий с минимальными доработками. Новый алгоритм представляет собой кардинально иной подход, который успешно преодолевает «барьер сортировки», обеспечивая лучшие теоретические результаты без необходимости в сортировке. Несмотря на рецензирование на конференции ACM Symposium on the Theory of Computing, практическое значение этого алгоритма вызывает вопросы. Дейкстра работает со скоростью порядка n log n + m, тогда как новый метод демонстрирует m log2/3 n. Однако в небольших сетях менее эффективное решение может быть быстрее. На практике важны и другие факторы, такие как скорость обнаружения сбоев и время обработки пакетов, которые также оптимизировались на протяжении лет. Таким образом, алгоритм Дейкстры продолжает оставаться предпочтительным, поскольку легко понимаем, чем более сложные методы. Сложность нового алгоритма может оттолкнуть практиков от его внедрения.