- 現在
- キュー内
- 確定
- 経路
ダイクストラ法
ダイクストラ法は、町と町を結ぶ道路のようにエッジに長さがあるとき、スタートから他のすべてのノードへの最短ルートを求めます。スタートから外へ広がりながら、まだ終わっていない最も近いノードを常に取り出します。ノードをクリックしてそこから始め、必要ならゴールを選び、ステップごとに進めて、キュー、短い道が見つかるたびに下がる距離、そして現れる最短経路を見てみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこへの最短経路を探します。各エッジの数字はその長さ、各ノードの数字はその時点での最短距離で、グラフの下の列がキューです(近い順)。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- ノードをクリックしてスタートにします。経路を探すには、クリックを「ゴール」に切り替えて別のノードをクリックします。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
- グラフの下のキューと各ノードの距離に注目しましょう。「新しいグラフ」で別のグラフを試せます。
ダイクストラ法のしくみ
スタートの距離を 0、他のノードをすべて無限大とし、スタートをキューに入れます。あとは繰り返しです。キューの中で距離が最小のノードを取り出し、その距離を確定とします。まだ確定していない隣接ノードそれぞれについて、エッジの長さをそのノードの距離に足します。その和が隣接ノードのそれまでの距離より短ければ、それが新しい距離になり、そのノードがそこへの道として記録され、隣接ノードがキューになければキューに加わります。キューが空になると、到達できるすべてのノードの最短距離が決まっています。
最も近いノードが確定する理由
あるノードがキューの中で最も近いとき、そこへの他のどの道も、グラフの終わった部分からキュー内のどこかのノードを通って出ていく必要があります。そのノードは少なくとも同じだけ遠く、その後に足すエッジは負になりません。だから他の道のほうが短くなることはありません。ゴールが最初に到達したときではなくキューから取り出されたときに初めて確実になるのも、ダイクストラ法が負のエッジでうまくいかないのも、このためです。負のエッジがあるときはベルマン–フォード法が必要です。すべてのエッジの長さが 1 なら、ダイクストラ法は幅優先探索と同じ動きをします。
よくある質問
ダイクストラ法とは何ですか?
エッジの長さが 0 以上のグラフで、1 つのスタートノードから他のすべてのノードへの最短経路を求める方法です。まだ終わっていない最も近いノードを繰り返し取り出し、その距離を確定させ、そのエッジを使って隣接ノードの距離を縮めます。
ダイクストラ法はなぜ負のエッジで使えないのですか?
ノードがキューの中で最も近くなった時点で、その距離を確定させるからです。後で見つかった負のエッジが、もっと短い道でそのノードに戻ってくる可能性があり、確定した距離が誤りになりえます。ベルマン–フォード法は、合計が負になる閉路がない限り、負のエッジを扱えます。
ダイクストラ法と BFS の違いは何ですか?
幅優先探索はエッジの本数を数え、普通のキューを使います。ダイクストラ法はエッジの長さを足し合わせ、常に最も近いノードを返す優先度付きキューを使います。すべてのエッジの長さが 1 なら、どちらも同じ距離を求めます。
ダイクストラ法はどのくらい速いですか?
優先度付きキューに二分ヒープを使うと、ノード数 V、エッジ数 E に対して処理量は (V + E) log V に比例して増えます。フィボナッチヒープなら E + V log V です。このアプリはキューをソート済みリストで持っています。表示が簡単で、小さなグラフには十分です。
グラフはどこかに送信されますか?
いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ