🚨 41 年かけて制作されましたが、ダイクストラはもはや無敵ではありません。 清華大学、スタンフォード大学、MPI for Informaticsのチームは、実際の非負の重みを持つ有向グラフの単一ソース最短経路の境界を破る最初の決定論的アルゴリズムを達成しました。 💡 新しいランタイム: O(m log^(2/3) n) 📜 古いベスト: ダイクストラ + フィボナッチ ヒープ = O(m + n log n) そのカギ。ダイクストラの「フロンティア」アイデアとベルマン・フォードのリラックスのハイブリッドで、ヒープを小さく保ち、古典的なソートの障壁を回避する再帰的なフロンティアパーティションのトリックを備えています。 インパクト： ⚡ GPS再計算の高速化 🚦 よりスムーズな交通の流れ 📦 より安い配送 🌐 より迅速なネットワークルーティング 📚 SSSP のアルゴリズムの章を書き直す時が来ました 1984年以来、有向SSSPの真の高速化は、決定論的です。