平成26年 秋期 応用情報技術者 午前 問5

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


 ア  V 4V 5V 6  イ  V 4V 6V 5
 ウ  V 5V 4V 6  エ  V 5V 6V 4


答え イ


解説
頂点V 1からV 4への最短所要時間はV 1−(1)→V 3−(1)→V 2−(1)→V 4の3
頂点V 1からV 5への最短所要時間はV 1−(1)→V 3−(1)→V 2−(1)→V 4−(2)→V 5の5
頂点V 1からV 6への最短所要時間はV 1−(1)→V 3−(1)→V 2−(1)→V 4−(1)→V 6の4
なので短い順に並べるとV 4V 6V 5(イ)になる。


キーワード
・クリティカルパス

キーワードの解説
  • クリティカルパス(critical path)
    生産工程やシステム開発プロジェクトなどで、並列作業や従属関係(前工程が終わらないと次工程に進めないなど)にある複数の作業のうち、開始から終了までをつなぐ時間的余裕のない一連の作業の集まりのことです。
    クリティカルパスにある作業に遅れが生じると生産工程やプロジェクト全体も遅れが発生します。
    また、電子回路において最終的な回路の出力に影響を与える部分のこともクリティカルパスと呼びます。(この場合、クリティカルパス以外の部分回路は冗長な回路になります。)

もっと、「クリティカルパス」について調べてみよう。

戻る 一覧へ 次へ