エドガー・ダイクストラによって考案された最短経路探索アルゴリズム。ルーターやナビゲーションシステムの経路探索に利用される。各分岐点間のコストをもとに最短コストで目的地に到達できる分岐点の選択順序を導き出す。
- 隣接経路の設定
- 経路探索
- Aからの最短コストを求める場合、まずAの配列上にある隣接する各分岐点B及びCまでのコストを算出する。
- 続いて順番に分岐点のAからのコストと経由点を求めていく。この際、求めたコストが以前に求めたコストよりも小さければこちらを採用する。
- 上記を分岐点の数分繰り返すととAからすべての分岐点への最短経路と経由点が導き出される。
- 例えばAからGへの最短経路はGの最短経路がD経由、Dの最短経路がE経由、Eの最短経路がC経由ということになる。
探索対象となる経路を設定する。経路は各分岐点を2次元配列とし、各径路への移動の可否を設定する。
| A | B | C | D | E | F | G | |
|---|---|---|---|---|---|---|---|
| A | 0 | 2 | 3 | null | null | null | null |
| B | 2 | 0 | 1 | 5 | null | null | null |
| C | 3 | 1 | 0 | 5 | 1 | null | null |
| D | null | 5 | 5 | 0 | 2 | 1 | 4 |
| E | null | null | 1 | 2 | 0 | null | null |
| F | null | null | null | 1 | null | 0 | null |
| G | null | null | null | 4 | null | null | 0 |
| B | C | D | E | F | G | |
|---|---|---|---|---|---|---|
| 1回目(Aの隣接) | A,2 | A,3 | ∞ | ∞ | ∞ | ∞ |
| 2回目(Bの隣接) | A,2 | A,3 | B,7 | ∞ | ∞ | ∞ |
| 3回目(Cの隣接) | A,2 | A,3 | B,7 | C,4 | ∞ | ∞ |
| 4回目(Dの隣接) | A,2 | A,3 | E,6 | C,4 | D,7 | D,10 |
| 5回目(Eの隣接) | A,2 | A,3 | E,6 | C,4 | D,7 | D,10 |
| 6回目(Fの隣接) | A,2 | A,3 | E,6 | C,4 | D,7 | D,10 |
| 7回目(Gの隣接) | A,2 | A,3 | E,6 | C,4 | D,7 | D,10 |
| 隣接 | コスト | |
|---|---|---|
| A | A | 0 |
| B | A | 2 |
| C | A | 3 |
| D | E | 6 |
| E | C | 4 |
| F | D | 7 |
| G | D | 10 |