平成26年度秋期 ITストラテジスト 午前Ⅰ 問3

重み付きグラフと経路探索

経路の所要時間の計算方法と、複数の経路を比較する手順を調べておきましょう。

この問題で問われていること

同じ出発点と到着点を結ぶ経路が複数あるとき、どのように所要時間を比較できるでしょうか。

重み付きグラフと経路探索

同じ出発点と到着点を結ぶ経路が複数あるとき、どのように所要時間を比較できるでしょうか。

確認ポイント

• 複数の区間を通る経路の所要時間は、各区間の数値からどのように計算しますか。
• 直接つながる経路と、別の頂点を経由する経路を比較する例を調べられますか。
• 経路の候補を見落とさないために、頂点のつながりをどのように書き出しますか。 所要時間が同じ点がある場合、問題文の並べ替え規則をどのように適用しますか。

正解

イ

解説

添付の公式解答表では，問3の正答は「イ」です。添付の公式問題ページのグラフから，V₄へはV₁→V₃→V₂→V₄を通ると1＋1＋1＝3で最短となる。V₆へはその経路からV₄→V₆へ進むと3＋1＝4，V₅へはV₄→V₅へ進むと3＋2＝5で，それぞれ最短となる。したがって，短い順はV₄，V₆，V₅となる。同じ最短所要時間の頂点はないため，添字による順序の調整は不要です。

添付の公式解答表では，問3の正答は「イ」です。添付の公式問題ページのグラフから，V₄へはV₁→V₃→V₂→V₄を通ると1＋1＋1＝3で最短となる。V₆へはその経路からV₄→V₆へ進むと3＋1＝4，V₅へはV₄→V₅へ進むと3＋2＝5で，それぞれ最短となる。したがって，短い順はV₄，V₆，V₅となる。同じ最短所要時間の頂点はないため，添字による順序の調整は不要です。

選択肢ア

誤り。V₅への最短所要時間は5，V₆へは4なので，V₆をV₅より先に並べる必要がある。

選択肢イ（正解）

正しい。最短所要時間はV₄が3，V₆が4，V₅が5となり，短い順に並んでいる。

選択肢ウ

誤り。V₅への最短所要時間は5で，V₄への3とV₆への4より長いので，V₅は最後になる。

選択肢エ

誤り。最短所要時間はV₄が3，V₆が4，V₅が5であり，この選択肢は長い順に並んでいる。

学習のポイント

同じ出発点と到着点を結ぶ経路が複数あるとき、どのように所要時間を比較できるでしょうか。