FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次のダイクストラ法で、頂点1から頂点5への最短距離はどれか。…
問題
次のダイクストラ法で、頂点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
頂点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を更新するため、最初に見た経路で確定しません。
仕組みの核心：ダイクストラ法は「未確定の中でdistが最小の頂点を確定させ、二度と更新しない」という貪欲法です。本問でもdist4は6→5と暫定値が下がった後に確定しました。確定済みの値を見直さずに済むのは辺の重みが非負だからで、負の重みがあると最短性が崩れる点が前提として重要です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。