41年ぶりに新しい最短経路アルゴリズムを発見
(arxiv.org)中国の清華大学（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 より小さく増えるため）、ノード数が非常に大きい場合には差が大きくなる。
18件のコメント
2000年代末に車載ナビゲーションソフトウェア企業で働きながら経路探索モジュールを開発していた思い出(?)がよみがえりますね。
Dijkstraはナビゲーションの経路探索には遅すぎて使わず、ヒューリスティックを改良したバージョンであるA* (A Star) 探索を使います。調べてみると、A*はSSSPではなくSPSP (Single-Pair Shortest Path) アルゴリズムなんですね。
スパースな場合に高速なアルゴリズムを上回ったと言うには、やや曖昧な気がします
CLRS が改訂されてからまだそれほど経っていないはずなのに、また新版を出すんですか
昔登場し、今もなお人気のあるバンドであるビートルズやオアシスの、41年ぶりの新しいアルバムが出たような感覚ですね。まずは驚きと興味をそそられます（笑）
アメリカにはすでにあったのかも？ すごい……
美しいね、すごい
最近の中国は勢いがあるね
アルゴリズム名がどう決まるのか気になる
その制約条件で、きっと誰かがもうすぐ Baekjoon に問題を出すんでしょうね。ワクワクします
懐かしのダイクストラ…
うわ…すごいですね…
すごいですね。
うわあ……
これはいけますね…
うおお~~
いや……。
アルゴリズムの授業内容が増えそうですね（笑）
やれやれ…