最短経路は単純な問題です。非負の実数の辺重みを持つ有向グラフが与えられたとき、DijkstraのアルゴリズムはFibonacciヒープを用いてO(m + n log n)時間で動作します。m ≥ nの場合、他の決定論的アルゴリズムはO(m log^{2/3} n)（2025年のブレークスルー）およびO(m √log n + √(mn log n log log n))（2026年のフォローアップ）を達成します。

約15時間と733メッセージの後、私のエージェントは新しいアルゴリズムC-HDを提案し、Leanで検証しました。これは局所探索をうまく処理し、優先度比較を使用し、新たに遭遇した頂点を未探索の葉としてカウントします。慎重な辺の削除と有界局所探索により局所不変量を維持し、認定範囲m ≤ n⌊⌊log₂ n⌋^{3/4}⌋内でO(n + m + m log(2 + m/(n+1)) + m^{1/3} (n log(n+2))^{2/3})を達成します。

C-HDは、ソースとフロンティアからの有界局所探索を実行し、新たに遭遇した頂点をカウントし、探索木とピボットを使用して再帰的作業を整理することにより、繰り返しの探索とデータ構造の作業を削減します。これはソートされた出辺リストに依存しています。小さいまたは範囲外の入力の場合、開始時にO((n+1)(m+1))の実行時間を持つ別のBellman–Fordアルゴリズムが選択されます。