アルゴリズムとプログラミング
基本情報技術者試験｜重み付き有向グラフで、辺の重みがA→B:2、A→C:5、B→C:1、B→D:6、C→D:2、C→E:7、D→E:…
重み付き有向グラフで、辺の重みが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を取り違えている。
アルゴリズムとプログラミングの他の問題
5頂点A〜Eの連結な無向グラフがあり、辺と重みはA-B:1、A-C:2、B-C:2、C-D:3、B-D:4、D-E:5、C-…動的計画法(DP)の基本的な考え方を最も適切に説明したものはどれか。貪欲法(グリーディ法)に関する説明として最も適切なものはどれか。次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…
この問題の「深掘り・誤答の完全解説・覚え方」は、登録すると読めます。
基本情報技術者試験は全4,036問。公開しているのはその一部で、登録すると残りも一問ごとにAI解説つきで解けます。SRS暗記カード・全真模試・弱点診断まで。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
作成・校閲：ukamiru編集部 · 基本情報技術者試験 過去問 · fe-a3-0141