Dijkstra法を超えるアルゴリズムが話題に

最短経路問題といえばDijkstra法。情報系の授業で最初に学ぶ古典的なアルゴリズムの一つですよね。1956年にエドガー・ダイクストラが考案して以来、カーナビ、ネットワークルーティング、ゲームAIなど、あらゆる場面で使われ続けてきました。

そのDijkstra法よりも高速に動作する新しいアルゴリズムが、最近Hacker Newsで話題になっています。今回は、この新手法の考え方と、実際にどの程度速いのかを調べてみました。

Dijkstra法のボトルネックはどこにあるのか

まずDijkstra法の計算量をおさらいしておきます。優先度キュー（二分ヒープ）を使った場合、計算量は O((V + E) log V) です。Vが頂点数、Eがエッジ数ですね。

この計算量は理論的にはかなり効率的なのですが、実際の大規模グラフでは「全頂点を一律に探索する」という性質がネックになることがあります。たとえば、地図データのように空間的な構造を持つグラフでは、ゴールの方向がわかっているのにわざわざ逆方向のノードまで展開してしまうケースが生じます。

A*アルゴリズムはヒューリスティック関数でこの問題を緩和しますが、今回の新手法はまた別のアプローチを取っています。

新しいアプローチ：前処理で探索空間を絞り込む

話題になっているアルゴリズムの核心は、「前処理（プリプロセス）」にあります。グラフの構造を事前に分析して、実行時の探索対象を大幅に減らす仕組みですね。

具体的には、以下のような手法が組み合わされています。

  • Contraction Hierarchies（CH）：重要度の低い頂点を事前に「縮約」して、主要なルートだけを残す
  • Hub Labeling：各頂点に「ハブ」となる頂点のリストを付与し、2点間の最短距離をラベルの交差で求める
  • Partition-based手法：グラフを領域に分割し、領域間の最短経路を事前計算

これらの手法は個別には以前から研究されていましたが、組み合わせ方と実装の最適化によって、KIT（カールスルーエ工科大学）のルート計画グループなどで実用レベルの性能が実証されています。

実際のベンチマーク結果を見てみる

ヨーロッパの道路ネットワーク（約1,800万頂点、4,200万エッジ）で比較すると、その差は圧倒的です。

  • Dijkstra法：平均500ミリ秒前後
  • A*：平均200ミリ秒前後
  • Contraction Hierarchies：平均0.5ミリ秒以下
  • Hub Labeling：平均マイクロ秒オーダー

桁が3つ以上違うのは驚きですよね。ただし、前処理に数分から数時間かかるというトレードオフがあります。つまり、頻繁にグラフ構造が変わるようなケースには向いていません。

逆に、道路ネットワークのようにグラフがほぼ静的な場合は、前処理のコストを十分に回収できるということです。Google Mapsの経路検索も、内部的には類似の前処理ベースの手法を使っているといわれています。

どんな場面で使えるのか

この手法が特に力を発揮するのは、以下のようなケースです。

  • カーナビ・経路案内（静的なグラフ、クエリ頻度が高い）
  • 物流の配送ルート最適化
  • ネットワークルーティングの事前計算
  • ゲームのマップ上のパスファインディング

一方で、ソーシャルグラフのように動的に変化するネットワークや、エッジの重みが頻繁に更新される場面では、従来のDijkstra法やA*の方が適している場合もあります。用途に応じた使い分けが大事ですね。

Valhalla（オープンソースのルーティングエンジン）やOSRMでは、実際にContraction Hierarchiesが実装されているので、試してみたい方はこのあたりから触ってみると良いかもしれません。

関連記事

まとめ

「Dijkstraより速い」というのは、正確にはDijkstra法そのものを改良したというより、前処理という新しいフェーズを導入することで実行時のクエリを高速化したという話でした。問題設定によって最適なアルゴリズムは変わりますが、静的グラフ×高頻度クエリの組み合わせでは圧倒的な差が出るのは間違いなさそうです。

アルゴリズムの世界は奥が深いですね。参考になれば幸いです。