Революция в поиске кратчайшего пути. Новый алгоритм обгоняет даже Дейкстру

Много лет алгоритм Дейкстры считался пределом скорости для поиска кратчайших путей: O(m + n log n). Дальше были только мечты и статьи по типу «а что если…».

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

Секрет прост: вместо одной глобальной сортировки вершин задача режется на компактные порции. Идеи Дейкстры смешали с Беллманом–Фордом — приоритеты, несколько проходов по рёбрам и умная работа с фронтиром.

В итоге прежние «узкие» места исчезли, а скорость выросла.

@your_tech