基本情報技術者試験「グラフアルゴリズム」の問題
重み付き有向グラフで、辺の重みがA→B:2、A→C:5、B→C:1、B→D:6、C→D:2、C→E:7、D→E:1である。頂点Aから頂点Eへの最短経路の重みの合計はいくらか。
ア重み6
イ重み9
ウ重み12
エ重み7
正解
ア．重み6
各頂点への最短距離を順に確定すると、B=2、C=min(5,2+1)=3、D=min(2+6,3+2)=5、E=min(5+2,3+7,5+1)=6となる。経路A→B→C→D→Eで2+1+2+1=6が最短のため正しい。
?選択肢ごとの解説
ア ○各頂点への最短距離を順に確定すると、B=2、C=min(5,2+1)=3、D=min(2+6,3+2)=5、E=min(5+2,3+7,5+1)=6となる。経路A→B→C→D→Eで2+1+2+1=6が最短のため正しい。
イ ×合計9はA→C→D→E(5+2+1=8)やA→B→D→E(2+6+1=9)など、より良い経路へ更新する処理を行わず途中経路で確定した誤りである。
ウ ×合計12はA→C→E(5+7=12)など重みの大きい辺をそのまま選び、緩和による更新を怠った誤りである。
エ ×合計7はA→B→C→Eの一部誤計算やD経由の比較漏れによる値で、E直前の最短D=5+辺1=6を取り違えている。
✎くわしく
ダイクストラ法は確定済み頂点から隣接頂点の距離を緩和(より短ければ更新)し、未確定で最小距離の頂点を順に確定する。負の重みがなければ最短を保証する。本問はCをB経由で3に更新できる点が最短発見の鍵である。
✓本番での押さえどころ
試験のコツ
各頂点の暫定距離を表にし、確定するたび隣接を更新する。負の辺がなければダイクストラで最短を確定できる。
覚え方
ダイクストラは『近い頂点から確定し、隣に行ける最短を上書きしていく』波及、とイメージする。
よくある誤り
最初に見つけた経路で確定し、後からより短い経路への更新(緩和)を忘れる誤りが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0141