ダイクストラ法
ルート検索アプリは、あなたの家の玄関からほぼどこへでも最速の道を知っています。その考え方の中心にあるのが、エドガー・ダイクストラが 1956 年に 20 分ほどで考え出したアルゴリズムです。スタートから外へ広がり、常に最も近い場所から先に確定させるのです。
考え方
長さの異なる道路で結ばれた町を思い浮かべてください。問題は、自分の町から他のすべての町への最短の道は何か、です。どの道路も同じとみなせるなら幅優先探索で答えられますが、ここでは道路の数が多いルートのほうが短いこともあります。ダイクストラ法は、町ごとにこれまでに見つかった最短距離を持ち、距離が確実になった町の領域を広げていきます。そのとき常に、まだ確実でない最も近い町を加えます。
ステップごとに
スタートの距離を 0、他のノードをすべて無限大にします。スタートを優先度付きキューに入れます。優先度付きキューとは、距離が最小のノードを常に渡してくれるキューです。そのノードを取り出すと、その距離は確定です。まだ確定していない隣接ノードそれぞれについて、このノードを通る距離、つまりこのノードの距離にエッジの長さを足した値を求めます。それが隣接ノードのそれまでの距離より短ければ、距離を下げ、このノードをそこへの道として記録し、隣接ノードをキューに入れます。これをエッジの緩和といいます。キューが空になるまで、またはゴールが取り出されるまで繰り返します。
例
エッジ A–B(長さ 4)、A–C(1)、B–C(2)、B–D(1)、C–D(5)、D–E(3)があり、A から始めるとします。A を取り出すと、B の距離は 4、C の距離は 1 になります。C が最も近いので 1 で確定し、C を通ると B は 1 + 2 = 3 に下がり、D は 1 + 5 = 6 になります。次は B が最も近く、3 で確定し、B を通ると D は 3 + 1 = 4 に下がります。D は 4 で確定し、E は 4 + 3 = 7 になります。つまり A から E への最短の道は A → C → B → D → E で、長さは 7 です。A → B → D → E のほうがエッジは少ないのですが、長さは 8 です。
正しい理由
ノード X がキューの中で最も近く、距離が d だとします。スタートから X への他のどの道も、どこかで確定済みノードの領域を出なければならず、その領域の外で最初に到達するノードはキューの中にあるので、すでに d 以上離れています。負のエッジはないので、残りの道でそれが短くなることはありません。したがって d が X への最短距離です。負のエッジがあるとこの議論は成り立たず、代わりにすべてのエッジを何度も緩和するベルマン–フォード法を使います。
歴史と用途
エドガー・W・ダイクストラは 1956 年、アムステルダムの新しいコンピュータ ARMAC を披露するために、オランダの都市間のルートを求めるこのアルゴリズムを考案し、1959 年に発表しました。同じ考え方は、より賢いキューと組み合わせて、ルート検索アプリや、OSPF や IS-IS などのインターネットのルーティングプロトコルで使われています。これらはデータがルーター間を通る最短の道を求めます。A* 探索は残りの距離の見積もりを加えるので、ゴールへ向かって進み、調べるノードを減らせます。
試してみよう
アプリを開いて「ステップ」を押してください。エッジの数字はその長さ、各ノードの数字はその時点での距離です。キュー内のノードは青、確定したノードは緑で、グラフの下のキューにはそれらが近い順に距離とともに並びます。遠回りに見えるルートが実は短いとわかって距離が下がる瞬間に注目し、ゴールを選んで、ゴールが確定したとたんに探索が止まるのを確かめましょう。
よくある質問
ダイクストラ法の計算量は?
優先度付きキューによって変わります。単純なリストならノード数 V に対して O(V²)、二分ヒープならエッジ数 E に対して O((V + E) log V)、フィボナッチヒープなら O(E + V log V) です。最後のものは 1984 年にマイケル・フレッドマンとロバート・タージャンが示しました。
ダイクストラ法は負のエッジの重みを扱えますか?
いいえ。ノードがキューの中で最も近くなったら、その距離はもう改善しないと仮定していますが、負のエッジはこれを崩すことがあります。負のエッジがあるグラフにはベルマン–フォード法を使ってください。
ダイクストラ法はすべてのノードへの経路を求めますか?
はい。最後まで実行すると、スタートから到達できるすべてのノードへの最短距離が得られ、記録したノードが最短経路の木を作ります。経路が 1 本だけ必要なら、ゴールが確定した時点で止めると処理を省けます。
ダイクストラ法と A* はどう関係していますか?
A* 探索は、ヒントを加えたダイクストラ法です。これまでの距離に、地図上の直線距離のような残りの距離の見積もりを足した値でキューを並べます。見積もりがよければ、はるかに少ないノードを調べるだけで同じ最短経路を見つけます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ダイクストラ法を試す