確定
キュー内
調べたエッジ

  • 現在
  • キュー内
  • 確定
  • 経路
ノードのクリックで設定

ダイクストラ法についてもっと見る

ダイクストラ法

ダイクストラ法は、町と町を結ぶ道路のようにエッジに長さがあるとき、スタートから他のすべてのノードへの最短ルートを求めます。スタートから外へ広がりながら、まだ終わっていない最も近いノードを常に取り出します。ノードをクリックしてそこから始め、必要ならゴールを選び、ステップごとに進めて、キュー、短い道が見つかるたびに下がる距離、そして現れる最短経路を見てみましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこへの最短経路を探します。各エッジの数字はその長さ、各ノードの数字はその時点での最短距離で、グラフの下の列がキューです(近い順)。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. ノードをクリックしてスタートにします。経路を探すには、クリックを「ゴール」に切り替えて別のノードをクリックします。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
  3. グラフの下のキューと各ノードの距離に注目しましょう。「新しいグラフ」で別のグラフを試せます。

ダイクストラ法のしくみ

スタートの距離を 0、他のノードをすべて無限大とし、スタートをキューに入れます。あとは繰り返しです。キューの中で距離が最小のノードを取り出し、その距離を確定とします。まだ確定していない隣接ノードそれぞれについて、エッジの長さをそのノードの距離に足します。その和が隣接ノードのそれまでの距離より短ければ、それが新しい距離になり、そのノードがそこへの道として記録され、隣接ノードがキューになければキューに加わります。キューが空になると、到達できるすべてのノードの最短距離が決まっています。

最も近いノードが確定する理由

あるノードがキューの中で最も近いとき、そこへの他のどの道も、グラフの終わった部分からキュー内のどこかのノードを通って出ていく必要があります。そのノードは少なくとも同じだけ遠く、その後に足すエッジは負になりません。だから他の道のほうが短くなることはありません。ゴールが最初に到達したときではなくキューから取り出されたときに初めて確実になるのも、ダイクストラ法が負のエッジでうまくいかないのも、このためです。負のエッジがあるときはベルマン–フォード法が必要です。すべてのエッジの長さが 1 なら、ダイクストラ法は幅優先探索と同じ動きをします。

よくある質問

ダイクストラ法とは何ですか?

エッジの長さが 0 以上のグラフで、1 つのスタートノードから他のすべてのノードへの最短経路を求める方法です。まだ終わっていない最も近いノードを繰り返し取り出し、その距離を確定させ、そのエッジを使って隣接ノードの距離を縮めます。

ダイクストラ法はなぜ負のエッジで使えないのですか?

ノードがキューの中で最も近くなった時点で、その距離を確定させるからです。後で見つかった負のエッジが、もっと短い道でそのノードに戻ってくる可能性があり、確定した距離が誤りになりえます。ベルマン–フォード法は、合計が負になる閉路がない限り、負のエッジを扱えます。

ダイクストラ法と BFS の違いは何ですか?

幅優先探索はエッジの本数を数え、普通のキューを使います。ダイクストラ法はエッジの長さを足し合わせ、常に最も近いノードを返す優先度付きキューを使います。すべてのエッジの長さが 1 なら、どちらも同じ距離を求めます。

ダイクストラ法はどのくらい速いですか?

優先度付きキューに二分ヒープを使うと、ノード数 V、エッジ数 E に対して処理量は (V + E) log V に比例して増えます。フィボナッチヒープなら E + V log V です。このアプリはキューをソート済みリストで持っています。表示が簡単で、小さなグラフには十分です。

グラフはどこかに送信されますか?

いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ