情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成26年度秋期 午前Ⅰ 問3: グラフに示される頂点 V₁ から V₄，V₅，V₆ の各点への最短所要時間を求め，短い順に並べたものはどれか。ここで，グラフ中の数値は各区間の所要時間を表すもの

問題本文

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

選択肢

• ア.V₄，V₅，V₆
• イ.V₄，V₆，V₅
• ウ.V₅，V₄，V₆
• エ.V₅，V₆，V₄

正解

イ. V₄，V₆，V₅

解説

始点V1からの最短時間をダイクストラ法で求める。V1→V3が1、V1→V3→V2が2、これを経由してV4はV2経由で3、V5はV4経由で5(2+2+1ではなくV4までの3+2)、V6はV4経由で4となる。よってV4=3、V6=4、V5=5で短い順はV4,V6,V5、イが正解。最短経路探索はルーティングや経路最適化の基礎アルゴリズム。

選択肢ごとの解説

• ア.V5(5)よりV6(4)の方が短いため、V4,V5,V6の並びは順序が逆で誤り。
• イ.V4=3、V6=4、V5=5で確定し、短い順がV4,V6,V5となるため正しい。
• ウ.最短はV5ではなくV4(3)が最小であり、先頭がV5となるこの並びは誤り。
• エ.V4を最後に置いているが実際はV4が最短で先頭に来るべきであり誤り。