Dijkstraが100万地点を探索するルートを、CCHは346地点で見つける

Dijkstra vs. A* vs. Contraction Hierarchies

ArcadeDBがフロリダ州の実道路網（107万交差点、271万道路区間）でDijkstra、A*、Customizable Contraction Hierarchies（CCH）を比較した。TallahasseeからCoral Gablesまで同じルートを返すのに、Dijkstraは1,029,617交差点、A*は840,138交差点を処理するのに対し、CCHはわずか346交差点。クエリ時間は0.039ms対99msと約2,500倍の差で、階層の構築は一度きり約7秒。交通情報の更新も0.9msで階層に反映され、常に正確な経路を返す。