グラフに示される頂点V1からV4、V5、V6の各点への最短所要時間を求め、短い順に並べたものはどれか。
ここで、グラフ中の数値は各区間の所要時間を表すものとし、最短所要時間が同一の場合には添字の小さい順に並べるものとする。
ア | V4、V5、V6 |
イ | V4、V6、V5 |
ウ | V5、V4、V6 |
エ | V5、V6、V4 |
答え イ
【解説】
頂点V1からV4への最短所要時間はV1−(1)→V3−(1)→V2−(1)→V4の3
頂点V1からV5への最短所要時間はV1−(1)→V3−(1)→V2−(1)→V4−(2)→V5の5
頂点V1からV6への最短所要時間はV1−(1)→V3−(1)→V2−(1)→V4−(1)→V6の4
なので短い順に並べるとV4、V6、V5(イ)になる。
【キーワード】
・クリティカルパス