Научные учёные математики говорят что улучшили алгоритм поиска кратчайшего пути в графе, Дейкстры и других, кто его уже улучшал, до временной сложности O(m*log^(2/3)(n)) вместо O(m + n*log(n)). Я не смог продраться сквозь формальный язык формул и определений, поэтому почитал ещё обзор, где какая никакая мысль есть, а не просто обозначение события. Улучшили за счёт того, что выбирают часть вершин и считают пути до этой группы целиком, потом рекурсивно повторяют то же внутри группы, вроде как.

Ресурсов тратится больше и в целом сложнее получилось, но абстрактно быстрее. С точки зрения применимости в нашем деле предложенный алгоритм формально подходит, компьютерные сети подпадают в категорию разряженных графов. Но, подозреваю, что текущие решения так вылизали на аппаратно-программном уровне, что в абсолютных значениях выигрыша не будет. Тем более, сети где надо считать кратчайшие пути таким способом, мы научились делать совсем небольшими (внутри area OSPF, или L1 уровня IS-IS), а дальше всё сводится к дистанционно-векторным протоколам.