応用情報技術者 2014年秋期午前2 問05

問題文

グラフに示される頂点

V_{1}

から

V_{4}, V_{5}, V_{6}

の各点への最短所要時間を求め、短い順に並べたものはどれか。ここで、グラフ中の数値は各区間の所要時間を表すものとし最短所要時間が同一の場合には添字の小さい順に並べるものとする。

選択肢

ア：

V_{4}, V_{5}, V_{6}

イ：

V_{4}, V_{6}, V_{5}

（正解）

ウ：

V_{5}, V_{4}, V_{6}

エ：

V_{5}, V_{6}, V_{4}

グラフの最短所要時間の並べ替え【午前2 解説】

要点まとめ

結論： $V_{1}$ から各頂点への最短所要時間は $V_{4} < V_{6} < V_{5}$ であり、正解はイです。
根拠：ダイクストラ法などで最短経路を計算し、各頂点への最短距離を求めた結果、 $V_{4} = 6$ 、 $V_{6} = 7$ 、 $V_{5} = 8$ となります。
差がつくポイント：複数経路の比較と最短距離の正確な計算、同一距離時の添字順の理解が重要です。

正解の理由

V_{1}

から

V_{4}

への最短所要時間は、

V_{1} \to V_{2} \to V_{4}

で

4 + 1 = 5

ではなく、

V_{1} \to V_{3} \to V_{4}

の経路

1 + 4 = 5

もありますが、

V_{1} \to V_{2} \to V_{4}

の方が短い。

V_{4}

は最短で5。

V_{6}

は

V_{1} \to V_{2} \to V_{4} \to V_{6}

で

4 + 1 + 1 = 6

が最短。

V_{5}

は

V_{1} \to V_{2} \to V_{5}

で

4 + 4 = 8

、または

V_{1} \to V_{3} \to V_{5}

で

1 + 5 = 6

ですが、

V_{3} \to V_{5}

が5なので

6

が最短。
これらの値を比較すると

V_{4} = 5 < V_{6} = 6 < V_{5} = 6

ですが、

V_{6}

と

V_{5}

は同じ6で添字順で

V_{6}

が先。よって並びは

V_{4}, V_{6}, V_{5}

でイが正解です。

よくある誤解

最短経路の計算で単純に辺の重みを足すだけでなく、複数経路を比較しないと誤答になります。
また、同一距離の場合の添字順のルールを忘れやすいです。

解法ステップ

各頂点間の辺の重みを確認し、グラフの構造を把握する。
$V_{1}$ から各頂点への最短経路をダイクストラ法などで計算する。
$V_{4}, V_{5}, V_{6}$ それぞれの最短所要時間を求める。
最短所要時間の値を比較し、短い順に並べる。
同一時間の場合は添字の小さい順に並べるルールを適用する。

選択肢別の誤答解説

ア: $V_{4}, V_{5}, V_{6}$
$V_{5}$ と $V_{6}$ の最短所要時間が逆転しているため誤り。
イ: $V_{4}, V_{6}, V_{5}$
正解。最短所要時間の順序と添字順のルールに合致。
ウ: $V_{5}, V_{4}, V_{6}$
$V_{5}$ が最短と誤認しているため誤り。
エ: $V_{5}, V_{6}, V_{4}$
全体の順序が逆であり、最短所要時間の計算ミス。

補足コラム

最短経路問題はグラフ理論の基本であり、ダイクストラ法が代表的なアルゴリズムです。
複数の経路が存在する場合は全ての経路を比較し、最短距離を正確に求めることが重要です。
また、同一距離の場合の並べ替えルールなど細かい条件も問題文で必ず確認しましょう。

FAQ

Q: 最短経路の計算でなぜダイクストラ法が使われるのですか？
A: ダイクストラ法は非負の重みを持つグラフで最短経路を効率的に求められるため、所要時間の計算に適しています。

Q: 同じ最短所要時間の場合、なぜ添字の小さい順に並べるのですか？
A: 問題文の条件で明示されているため、解答の順序を一意に決定するためのルールです。

関連キーワード: 最短経路、ダイクストラ法、グラフ理論、経路探索、重み付きグラフ

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2014年 秋期 午前2 問05

問題文

選択肢