平成26年度 秋期 応用情報技術者試験 午前 問5
テクノロジ／アルゴリズムグラフに示される頂点 V1 から V4，V5，V6 の各点への最短所要時間を求め，短い順に並べたものはどれか。ここで，グラフ中の数値は各区間の所要時間を表すものとし，最短所要時間が同一の場合には添字の小さい順に並べるものとする。
出典：平成26年度 秋期 応用情報技術者試験 午前 問5
- アV4，V5，V6
- イV4，V6，V5
- ウV5，V4，V6
- エV5，V6，V4
正解：イ
解説
図のV1から各頂点への最短経路をダイクストラ法で求めます。V1→V3＝1，V1→V2はV1→V3→V2（1＋1＝2）の方が直接の4より短いのでV2＝2，V4はV2→V4（2＋1＝3）でV4＝3，V6はV4→V6（3＋1＝4）でV6＝4，V5はV4→V5（3＋2＝5）でV5＝5となります。したがって短い順はV4（3），V6（4），V5（5）です。
選択肢ごとの解説
- ア誤り。V2からV3への1の辺を経由する近道を考慮しないと，V5がV6より短いと誤認しますが，正しくはV6の方が短くなります。
- イ正しい。V4＝3，V6＝4，V5＝5の順に短くなります。
- ウ誤り。V1から直接V2へ向かう経路（4）だけで計算し，V3経由の短絡路を見落とした場合の誤りです。
- エ誤り。V4が最短であることは正しいですが，V5とV6の順序が逆になっています。