FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
次のダイクストラ法で，頂点1から頂点5への最短距離はどれか。
頂点1から5への最短距離を求める。
辺と重み: (1,2,2), (1,3,5), (2,3,1), (2,4,4), (3,4,2), (4,5,1)
整数型の配列: dist ← {0, ∞, ∞, ∞, ∞}
未確定頂点の中でdistが最小の頂点vを選び，vから出る辺でdistを更新する処理を繰り返す。
return dist[5]- ア 5
- イ 6
- ウ 7
- エ 8
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：6
正解：6
頂点1から直接3へ行く距離は5だが，1→2→3なら2+1=3なので更新される。さらに3→4で距離5，4→5で距離6となる。
| 確定頂点 | 主な更新 | dist[5] |
|---|---|---|
| 1 | dist2=2, dist3=5 | ∞ |
| 2 | dist3=3, dist4=6 | ∞ |
| 3 | dist4=5 | ∞ |
| 4 | dist5=6 | 6 |
最短経路は1→2→3→4→5で，距離は2+1+2+1=6。最初に見つかった経路で確定しない点が重要である。
選択肢の見分け方：7は1→2→4→5の距離，8は遠回りの値である。ダイクストラ法では，より短い経路が見つかったらdistを更新するため，最初に見た経路で確定しない。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。