令和３年度 技術士第一次試験問題【専門科目】
Ⅲ－４
各ノード間の移動コストが非負である場合の最短経路探索を行う際、Dijkstra のアルゴリズムがよく用いられる。Dijkstra のアルゴリズムを用いて下図の始点ノードＳから他のノードへの最短経路・コストを求める際に、Ｓからの最短経路が決定していくノードの順序として、最も適切なものはどれか。
① Ｓ Ａ Ｂ Ｃ Ｄ
② Ｓ Ａ Ｃ Ｂ Ｄ
③ Ｓ Ｂ Ａ Ｄ Ｃ
④ Ｓ Ｂ Ｄ Ａ Ｃ
⑤ Ｓ Ｂ Ｃ Ａ Ｄ
正解
④
解説
Dijkstra (ダイクストラ) のアルゴリズムは、各点までの距離を順番に確定していくアルゴリズムのことである。
手順は以下のとおりである。
(1) 始点を決め、始点のコストを0、始点以外の全てのノードまでのコストを最大値で初期化する。
(2) 始点を確定済みとし、始点に移動する。
(3) 移動したノードと隣接している未確定のノードまでの、始点からのコストをそれぞれ求め、それぞれを最小値で更新する。
(4) 未確定ノードの中から最小のコストのノードを確定済みとし、そのノードに移動する。
(5) (3),(4)を未確定ノードがなくなるまで繰り返す。
Ｓからの最短経路が決定していくノードの順序は以下のとおりである。
1) Ｓ:0、Ａ:∞、Ｂ:∞、Ｃ:∞、Ｄ:∞ で初期化する。
2) Ｓを確定済みとし、Ｓに移動する。
3) Ｓと隣接しているA、Ｂまでの、始点からのコストを求め、Ａ:10、Ｂ:5 として更新する。
4) 未確定ノードの中から最小のノードであるＢを確定済みとし、Ｂに移動する。
5) Ｂと隣接しているＡ、Ｃ、Ｄまでの、始点からのコストをそれぞれ求め、Ａ:8、Ｃ:14、Ｄ:7として更新する。
6) 未確定ノードの中から最小のノードであるＤを確定済みとし、Ｄに移動する。
7) Ｄと隣接しているＣまでの、始点からのコストをそれぞれ求め、Ｃ:13として更新する。
8) 未確定ノードの中から、最小のコストであるＡを確定済みとし、Ａに移動する。
9) Ａと隣接している未確定ノードはない。
10) 唯一残った未確定ノードＣを確定済みとする。
したがって、Ｓ ⇒ Ｂ ⇒ Ｄ ⇒ Ａ ⇒ Ｃの順に最短経路が決定していく。
| Ⅲ－３ | 目次 | Ⅲ－５ |