SC情報処理安全確保支援士試験 午前Ⅰ

平成26年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

グラフに示される頂点 V₁ から V₄,V₅,V₆ の各点への最短所要時間を求め,短い順に並べたものはどれか。ここで,グラフ中の数値は各区間の所要時間を表すものとし,最短所要時間が同一の場合には添字の小さい順に並べるものとする。
頂点V₁からV₆までを結ぶ重み付き無向グラフ。各辺の数値は所要時間を表す。
頂点V₁からV₆までを結ぶ重み付き無向グラフ。各辺の数値は所要時間を表す。

選択肢

  1. ア
    V₄、 V₅、 V₆
  2. イ
    V₄、 V₆、 V₅
  3. ウ
    V₅、 V₄、 V₆
  4. エ
    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₄,V₆,V₅の順)です。最短経路は,出発点から各頂点までの所要時間の合計が最小になる経路を探すことで求める。V₄へはV₁→V₃→V₂→V₄と進むと1+1+1=3で最短となる。V₆はV₄から直接つながるため,3+1=4が最短です。V₅もV₄から直接つながるため,3+2=5が最短です。3,4,5の順に並ぶので,添字による調整は不要です。

誤答の理由

ア:V₅(5)とV₆(4)の順が逆です。V₆の4はV₅の5より短いので,V₆を先に並べる必要がある。

ウ:V₅を先頭に置いている点が誤りです。V₅の5はV₄の3やV₆の4より大きいので,最後に並べる必要がある。

エ:長い順に並べている点が誤りです。V₄,V₆,V₅は3,4,5であり,短い順に並んでいる。

整理

「V₄→V₆→V₅の順に,経路の合計が3,4,5と増えていく」と確認すると取り違えにくい。最短経路問題は,始点に近い頂点から順に確定させていくダイクストラ法で解くのが一般的です。

選択肢ア

誤り。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であり,この選択肢は長い順に並んでいる。

学習のポイント

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

解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。

出典:独立行政法人 情報処理推進機構(IPA)平成26年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問3(公式資料:問題冊子(PDF) / 解答例)

関連する過去問一覧

IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針