平成26年度 秋期 午前 問5
基礎理論
最短経路に関する問題
グラフに示される頂点 V1 から V4，V5，V6 の各点への最短所要時間を求め，短い順に並べたものはどれか。ここで，グラフ中の数値は各区間の所要時間を表すものとし，最短所要時間が同一の場合には添字の小さい順に並べるものとする。
〔グラフ〕
置き方 … 左端 V1 ／ 上段 V2・V4 ／ 下段 V3・V5 ／ 右端 V6 辺は 10 本（数値は所要時間） 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
- アV4，V5，V6
- イV4，V6，V5
- ウV5，V4，V6
- エV5，V6，V4
答えと解説を見る
✓ これが正解イV4，V6，V5
解説
近い点から確定させると 3、4、5 の順です。
設問は、頂点 V1 から三つの頂点への最短所要時間を求め、短い順に並べさせています。見分けの軸は、直通の辺があってもそれが最短経路とは限らないという一点で、ここを外すとグラフの数値を目で足し比べることになり必ず崩れます。ですから V1 に近い頂点から順に確定させます。まず V1 から直に 1 で届く V3 が最も近く、これが確定します。次に V2 は直通の辺が 4 ですが、V3 を回れば 1 と 1 で 2 になるので、こちらが最短です。V4 は V2 から 1 なので 2 と 1 で 3、V3 から直に向かう道は 1 と 4 で 5 ですから、短いほうを採って 3 と決まります。V6 は V4 から 1 で届くので 3 と 1 で 4 です。V5 は V4 から 2 で 3 と 2 の 5 となり、V2 を回る道も V3 を回る道も V6 を回る道もいずれも 6 になるので、5 が最短です。結局この三つは 3、4、5 の順に遠くなり、V4、V6、V5 と並びます。経路で確かめると、三本とも V3 から V2 を通って V4 へ抜ける同じ背骨を共有しています。
ほかの選択肢はなぜ違うのか
- アV4，V5，V6：先頭の頂点は合っていますが、あとの二つが入れ替わっています。下辺と縦の辺の数値が大きいために遠く見える頂点が、実は背骨の終端から 1 だけで届くという関係を見落とすと、この並びになります。
- ウV5，V4，V6：V1 から下辺を通る道は 1 と 5 で 6 ですが、これを短く見誤り、いちばん近いものとして先頭に置いた形です。実際にはその頂点が三つの中で最も遠く、順序は逆向きになります。
- エV5，V6，V4：こちらも最も遠い頂点を先頭に置いており、さらに背骨の終端にある頂点を最後に回しています。近い順に確定させる手順を踏めば、その頂点が 3 で最初に来ることが分かります。
出典：平成26年度 秋期 応用情報技術者試験 午前 問5
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）