基本情報技術者 2015年 秋期 午前（科目A） 問51

アローダイアグラムで表されるプロジェクトの最短所要日数【午前2 解説】

要点まとめ

• 結論：プロジェクトの最短所要日数は120日で、クリティカルパスはノード1→2→4→5→6→7（ダミー含む）です。
• 根拠：各イベントの最早時刻を順に計算し、ノード6は最早で90日、最終ノード7は90＋30＝120日となるためです。
• 差がつくポイント：ダミー矢印は所要日数0でも前後関係を変え、イベントの最早時刻は「前任者の最大値」で決まる点に注意。

正解の理由

よくある誤解

• ダミー矢印を無視してノード5の最早時刻を50日（＝1→2→5）としたまま計算し、所要日数を110日と誤答する。ダミーは前後関係を変える。
• 単純に「経路ごとの合計時間」を比較して最大値を取るだけでなく、イベントの最早時刻は複数の到達パスの「最大値」を採る点を見落とす。
• ダミーの所要日数が表示されないからといって存在を無視すると、クリティカルパス判定を誤る。

解法ステップ

1. イベント1を時刻0とする。
2. 有向矢印の順に各イベントの最早時刻を計算（到達する前任者の最早時刻＋作業日数）し、複数前任者があれば最大値を採る。
3. ダミー（破線）は日数0だが依存関係を作るので最早時刻の最大値に影響する。
4. 最終イベント（ノード7）の最早時刻がプロジェクトの最短所要日数となる。

• ノード1 = 0
• ノード2 = 0 + 30 = 30
• ノード3 = 30 + 5 = 35
• ノード4 = max(30 + 30, 35 + 0) = max(60,35) = 60
• ノード5 = max(30 + 20, 60 + 0) = max(50,60) = 60
• ノード6 = max(35 + 40, 60 + 25, 60 + 30) = max(75,85,90) = 90
• ノード7 = 90 + 30 = 120

選択肢別の誤答解説

• ア: 115日 — 1→2→4→6→7（30＋30＋25＋30＝115）を見て選ぶ誤り。だがノード5経由（ダミー含む）でノード6の最早が90日になり全体は120日となる。
• イ: 120日 — 正解。ダミーがノード5を遅らせ、ノード5→6ルート（60＋30）がクリティカルとなるため最終は120日。
• ウ: 125日 — どの単一路径でも125にはならない。おそらく誤ってダミーに非ゼロ日数を加算したか、複数経路の合算ミス。
• エ: 130日 — 同様に計算ミス。全パスの最大でも130には達しないため不正解。

補足コラム

• AOA（Activity on Arrow）形式ではダミー作業が必要になることがあり、ダミーは論理的な依存関係を表すために使います。ダミーは持ち時間0ですが、イベント（ノード）の最早/最晚に影響を与えます。
• AON（Activity on Node）形式に変換するとダミーは不要になり、可視化と計算が直感的になる場合があります。試験では図の形式を正確に読み取り、最早時刻を「最大」で取る点を常に意識してください。

FAQ