1 歩ずつ動かす
| 頂点 | 距離 | 手前の頂点 | 確定した順 |
|---|---|---|---|
| A | 0 | なし | まだ |
| B | ∞ | なし | まだ |
| C | ∞ | なし | まだ |
| D | ∞ | なし | まだ |
| E | ∞ | なし | まだ |
| F | ∞ | なし | まだ |
- いま確定した頂点
- 確定した頂点 (右上の数は確定した順)
- まだ確定していない頂点 (下の数が距離)
- いま見ている辺
辺の上の数は辺の長さ、頂点の下の数は、いまわかっている開始の頂点からの距離です。∞ は、まだ行き方が見つかっていないことを表します。
1 歩目 / 全 24 歩見た辺 0 本確定 0 個
開始の頂点 A の距離を 0 にします。ほかの頂点は、まだ行き方が見つからないので ∞ です。
いま動いている疑似コードの行
- 1開始の頂点の距離を 0、ほかの頂点を ∞ にする
- 2確定していない頂点に、距離が ∞ でない物があるあいだ、次をくり返す
- 3その中で距離がいちばん小さい頂点 u を選んで、確定する
- 4u の隣 v と辺の長さ w を、名前の順に 1 つずつ見る
- 5dist[u] + w が dist[v] より小さければ、dist[v] を書き換える
- 6そうでなければ、何もしない
見本を変える
予想してみる
いまは 1 歩目です。
次に確定するのは、どの頂点でしょう。
今回わかること
- 辺ごとに長さが違うグラフで、開始の頂点から各頂点までの最短の距離を求める流れ
- 距離がいちばん小さい頂点から確定していく理由と、距離を書き換える条件
前提
- グラフの頂点と辺
- 幅優先探索 (近い順にたどる)
- 配列から最小の値を探す方法
どんな求め方か
ダイクストラ法は、辺ごとに長さが違うグラフで、開始の頂点から各頂点までの最短の距離を求める方法です。幅優先探索が辺の数で近い順に広げるのに対し、こちらは辺の長さを足した距離で近い順に広げます。
確定していない頂点のうち、距離がいちばん小さい物を選んで確定します。辺の長さが 0 以上なら、いちばん小さい物はもっと近い道が後から見つかることが無いからです。確定した頂点を通ると近くなる隣は、距離を書き換えます。
手順と具体例
- 1開始の頂点の距離を 0、ほかの頂点を ∞ にする
- 2確定していない頂点のうち、距離がいちばん小さい頂点を選んで確定する
- 3選んだ頂点の隣について、その頂点を通る距離を求める
- 4いまの距離より小さければ、隣の距離を書き換える
- 5選べる頂点が無くなるまで、2 から 4 をくり返す
| 確定した頂点 | 距離 | 書き換わった距離 |
|---|---|---|
| A | 0 | B は ∞ から 4、C は ∞ から 2 |
| C | 2 | B は 4 から 3、E は ∞ から 12 |
| B | 3 | D は ∞ から 8 |
| D | 8 | E は 12 から 10、F は ∞ から 14 |
| E | 10 | F は 14 から 13 |
| F | 13 | なし |
見る回数と計算量
| 数えるもの | 回数 | 計算量 |
|---|---|---|
| 頂点を選ぶ | 1 回につき、頂点を全部見て探す | O(V²) |
| 辺を見る | 辺 1 本につき 2 回 (両側から) | O(E) |
| 合わせて | 頂点を探す手間が大きい | O(V²) |
V は頂点の数、E は辺の数です。ここで見せた形は、頂点を選ぶたびに全部の頂点を見て最小を探すので、頂点を選ぶ手間が V の 2 乗になります。最小を取り出すのにヒープ (優先度付きキュー) を使うと、O((V + E) log V) まで減らせます。辺が少ない大きなグラフでは、こちらを使います。
使いどころ
向いているとき
- 辺ごとに長さが違うグラフで、最短の道を求めたいとき (道路の距離、通信の遅れ)
- 開始の頂点から、全部の頂点への最短の距離を一度に知りたいとき
向いていないとき
- 辺の長さが全部同じとき (幅優先探索のほうが簡単で速い)
- 辺の長さに負の数があるとき (確定した距離がくつがえるので、ベルマン・フォード法を使う)
コード
疑似コード
- 1開始の頂点の距離を 0、ほかの頂点を ∞ にする
- 2確定していない頂点に、距離が ∞ でない物があるあいだ、次をくり返す
- 3その中で距離がいちばん小さい頂点 u を選んで、確定する
- 4u の隣 v と辺の長さ w を、名前の順に 1 つずつ見る
- 5dist[u] + w が dist[v] より小さければ、dist[v] を書き換える
- 6そうでなければ、何もしない
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- なぜ距離がいちばん小さい頂点を先に確定してよいのですか？
- 辺の長さが 0 以上なら、ほかの未確定の頂点を回り道しても、距離は小さくなりません。足すたびに増えるだけだからです。だから、いちばん小さい頂点の距離は、そこで最短だと決まります。
- 辺の長さに負の数があるとどうなりますか？
- 確定したあとに、負の辺を通るほうが近い道が見つかることがあり、確定した距離が間違いになります。負の辺があるグラフには、ベルマン・フォード法を使います。
- 最短の道そのものは、どう求めますか？
- 距離を書き換えるとき、手前の頂点も覚えておきます。終点から手前の頂点をたどって開始の頂点まで戻り、並びを逆にすると、道すじになります。表の「手前の頂点」の列がその記録です。
