前回に続いて「なっとくアルゴリズム」を読んで理解したことのまとめです。
ダイクストラ法
幅優先探索ではスタート地点からゴール地点へ最短経路で移動する方法を割り出すことができた。
しかしこれは必ずしも最速の経路とは限らない。これらの辺に移動時間の情報を追加すると最も高速な経路が分かる。
最速の経路を見つけるにはダイクストラ法というアルゴリズムを使う。
ダイクストラ法のアルゴリズム
ダイクストラ法は次の4つのステップで構成される。
- 「最もコストが低い」ノードを探す。これは最も短い時間で移動できるノードである。
- このノードの隣接ノードのコストを更新する。
- グラフ内のノード毎に同じ作業を繰り返す。
- 最終経路を割り出す。
簡単なグラフで実際にダイクストラ法を適用してみる
このグラフを幅優先探索で最短経路を探した場合、次のように7分掛かることになる。
ダイクストラ法を使うと次のようになる。
ステップ1
START地点からの最もコストが低いノードを探す。ノードAとノードBへ移動するのに掛かる時間は次の通り。
| 親ノード | ノード | 掛かる時間 |
|---|---|---|
| START | A | 6 |
| START | B | 2 |
| – | GOAL | ∞ |
GOALまでの所要時間は現時点ではわからないので∞（無限大）にしておく。
上記の表から最も近いノードはBで2分の距離にあることがわかる。
ステップ2
ノードBからの辺をたどることにより、ノードBの全ての隣接ノードへ移動するのに掛かる時間を割り出す。
ノードAへの所要時間が6分だったが、ノードBを経由すると5分に短縮されることがわかったので、先ほどの表を更新する。また、GOALへの所要時間が∞から7分に短縮されることがわかったので、これも更新する。
| 親ノード | ノード | 掛かる時間 |
|---|---|---|
| B | A | 5 |
| START | B | 2 |
| B | GOAL | 7 |
ステップ3
上記ステップを繰り返す。ノードBでの作業は終わっているため、予想時間が次に短いノードAを対象にし、ステップ2でやったことを繰り返す。
GOALまでの所要時間が6分に短縮されることがわかったので表を更新する。
| 親ノード | ノード | 掛かる時間 |
|---|---|---|
| B | A | 5 |
| START | B | 2 |
| A | GOAL | 6 |
この時点で次の3つのことが判明している。
- ノードAまでの所要時間は5分
- ノードBまでの所要時間は2分
- GOALまでの所要時間は6分
ステップ4
最終経路を割り出す。
- GOALノードの親を確認すると、ノードAなので辿るのはこの辺になる。
- ノードAの親を確認すると、ノードBなので辿るのはこの辺になる。
- ノードBの親を確認すると、STARTノードなので辿るのはこの辺になる。
以上のことから、ダイクストラ法を使った最短経路は「START -> ノードB -> ノードA -> GOAL」となる。
ダイクストラ法の用語
グラフの各辺に数字が割り当てられている場合、この数字を「重み（weight）」と呼ぶ。
重みの付いたグラフを「重み付きグラフ（weighted graph）」と呼び、重みの付いていないグラフを「重みなしグラフ（unweighted graph）」と呼ぶ。
重みなしグラフで最短経路を割り出すには幅優先探索を使い、重み付きグラフで最短経路を割り出す場合にはダイクストラ法を使う。
グラフには閉路（circle）が含まれている場合がある。閉路が含まれたグラフとは下記のようなものを表す。
上記のグラフはノードAからノードBを辿って、またノードAに戻ってくることができる。この閉路を辿る経路は絶対に最短経路にはならない。
また、次のような無向グラフも両方のノードが互いを指しているので閉路となる。
閉路や無向グラフではダイクストラ法ではうまくいかない。ダイクストラ法がうまくいくのは有向無閉路グラフ（directed acyclic graph）だけである。
コメント