応用情報技術者アルゴリズムとデータ構造オリジナル・公式資料照合難易度★★★☆☆
有向グラフの辺と非負の重みはA→B:2、A→C:5、B→C:1、B→D:6、C→D:2だけである。AからDへの最短距離と経路はどれか。
A
5、A→B→C→D★ 正解
A→B→C→Dの重みは2+1+2=5で、他の候補経路7および8より短くなります。
B
7、A→C→D
この経路は実在し重み7ですが、Bを経由してCへ行くと5より短い距離3でCへ到達できます。
C
8、A→B→D
A→B→Dの重みは8ですが、B→C→Dを選ぶとその後の距離は1+2で済みます。
D
10、A→B→C→D
同じ経路の正しい合計は2+1+2=5です。A→Cの重み5を重複加算してはいけません。
解説
非負重みなのでDijkstra法が使えます。Aからの確定距離はB=2、C=3、D=5となります。
根拠資料・確認情報
対応範囲：2026年度 応用情報技術者試験
資料確認日：2026-10-28