FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：図の重み付き無向グラフで、SからGまでの最短距離はどれか。
問題
図の重み付き無向グラフで、SからGまでの最短距離はどれか。
- ア 12（正解）
- イ 11
- ウ 10
- エ 13
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目A範囲
正解と解説
正解：12
何を問う論点か：グラフ上でSからGまでの最短経路の距離を求める問題です。図の各辺の重みを足して、候補となる経路を比較していきます。
考え方：S→A→B→D→G は 4+1+4+3＝12 で、S→A→C→G の 4+5+7＝16 や S→B→D→G の 6+4+3＝13 より短くなります。したがって最短距離は12です。
誤答の見分け方：10や11は、図の辺を一部だけ足したり、存在しない近道を想定したときに出やすい値です。13は S→B→D→G だけを見てしまった場合の値になります。
押さえるポイント：最短経路は「それらしい経路」だけで判断しないのがコツです。各ノードへの暫定最短距離を更新していくと、図が複雑でも漏れを防げると覚えておくと迷いません。
他の選択肢はなぜ違う？
- イ辺の重みを1本足し落とすと出る値。経路の辺を図と1本ずつ照合すれば防げる。
- ウ実在しない近道を想定した値。図にある辺だけをたどると、どの経路も10には届かない。
- エS→B→D→G（6+4+3）だけを見た値。S→A→B→D→Gの12の方が短い。
この問題について
IPAが公開するシラバス・試験範囲・公開問題の出題形式を参考にした独自作成問題。公式問題・過去問題の転載ではありません。
公式試験問題、過去問題、公式サンプル問題、市販教材の問題文を転載したものではありません。