ソーティング・バリア

計算機科学における最短経路問題の理論的限界を指す用語。1956年に考案されたダイクストラ法は、優先度付きキューを用いて頂点を距離の昇順で確定させていくが、この操作は本質的にソーティング（並べ替え）と等価である。比較と加算のみを許す計算モデルにおいて、ソーティングにはO(n log n)の下限が存在するため、長年この壁を越えることは不可能と考えられてきた。2025年に発表された新アルゴリズムは、頂点を厳密な距離順に処理しない戦略をとることで、この40年来の壁を初めて打破した。