41年ぶりに新しい最短経路アルゴリズムを発見

中国の清華大学（Tsinghua University）の研究チームがスタンフォード大学と協力し、従来型の最短経路（single-source shortest path, SSSP）問題について、計算量の観点で大きな進展を達成した。 この研究は2025年のSTOCでBest Paper賞を受賞した。

従来広く使われてきた方法はダイクストラ（Dijkstra）アルゴリズムで、時間計算量は O(m + n log n)（n = ノード数、m = 辺数）という形である。
log n 項は優先度付きキュー（priority queue）やソート（sorting）に関連する部分で、過去40年間この部分を超える改善はなかった。

新しいアルゴリズムは時間計算量を O(m · log^(2/3) n) に削減した。
log^(2/3) n は log n よりも遅く増加するため（つまり log n より小さく増えるため）、ノード数が非常に大きい場合には差が大きくなる。