グラフに示される頂点V1からV4，V5，V6の各点への最短所要時間を求め，短い順に並べたものはどれか。ここで，グラフ中の数値は各区間の所要時間を表すものとし，最短所要時間が同一の場合には添字の小さい順に並べるものとする。
図の内容（文字）
頂点V1〜V6からなる無向グラフ。辺と所要時間は次のとおり。
V1−V2：4
V1−V3：1
V2−V3：1
V2−V4：1
V2−V5：4
V3−V4：4
V3−V5：5
V4−V5：2
V4−V6：1
V5−V6：2
平成26年度 秋期 応用情報技術者 問5
テクノロジ系
正解と解説
正解 イ
V1からの最短所要時間は、V4が3、V6が4、V5が5です。したがって短い順にV4、V6、V5となります。
V1から近い頂点を順に確定させます（ダイクストラ法）。V3はV1−V3で1です。V2はV1−V3−V2で1+1=2となり、直接の4より短くなります。V4はV2経由で2+1=3です。V3からの直接の4+1=5より短くなります。V6はV4経由で3+1=4です。V5はV4経由で3+2=5です。V2経由の2+4=6、V3経由の1+5=6、V6経由の4+2=6より短くなります。よって、V4（3）、V6（4）、V5（5）の順です。
ア：V6はV4経由で4、V5は最短でも5です。V6のほうがV5より短くなります。
ウ：V5の最短は5で、V4の3やV6の4より長くなります。V5を最初に置く並びにはなりません。
エ：V4はV1−V3−V2−V4で3となり、3点の中で最も短くなります。V4が最後になることはありません。
出典：平成26年度 秋期 応用情報技術者試験 問5
全年度から出題。10問で実力を判定します。登録不要。
出典：平成26年度 秋期 応用情報技術者試験 問5（独立行政法人情報処理推進機構）
解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方