情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成26年度秋期 午前Ⅰ 問3: グラフに示される頂点 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が最短で先頭に来るべきであり誤り。