エドガー・ダイクストラによって考案された最短経路探索アルゴリズム。ルーターやナビゲーションシステムの経路探索に利用される。各分岐点間のコストをもとに最短コストで目的地に到達できる分岐点の選択順序を導き出す。
探索対象となる経路を設定する。経路は各分岐点を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 |