FE SUBJECT A
基本情報技術者 科目Aの問題解説
問題
図の重み付き無向グラフで、SからGまでの最短距離はどれか。
- ウ 10
- イ 11
- ア 12
- エ 13
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目A範囲
正解と解説
正解：12
正解：12
考え方：重み付き無向グラフで，S から G までの各経路の重み（距離）の合計を比べ，最小のものを選ぶ。図の辺をたどると S→A→B→D→G が 4+1+4+3＝12 で最短になる。
誤答の理由：他の経路（より大きい合計）を選んだ値や，一部の辺を見落とした値が誤答。すべての経路を比較する。
注意点：最短経路問題は，各経路の重みの和を漏れなく比較する。複雑な図ではダイクストラ法のように，始点から確定した最短距離を広げていくと数え漏れを防げる。
この問題について
IPAが公開するシラバス・試験範囲・公開問題の出題形式を参考にした独自作成問題。公式問題・過去問題の転載ではありません。
公式試験問題、過去問題、公式サンプル問題、市販教材の問題文を転載したものではありません。