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