応用情報技術者 2009年 秋期 午前2 問50

クリティカルパス判定【午前2解説】

正解の理由

解法ステップ

1. 図の矢印の向き（有向性）と所要日数を確認する。ダミーは所要日数 0 であることを確認する。
2. 開始から終了へ到達する「実際にたどれる経路」をすべて列挙する（矢印の向きを守る）。
3. 各経路について所要日数を合計する。
4. 合計が最大の経路がクリティカルパスであると判定する。

• A → D → H : $1+3+4=8$ 日
• A → C → E → G : $1+3+4+5=13$ 日
• B → E → G : $5+4+5=14$ 日（最長）
• A → D → F(ダミー0) → G : $1+3+0+5=9$ 日（存在するが短い）

選択肢別の誤答解説

• ア: A→C→E→G
  • 有効な経路で所要日数は $1+3+4+5=13$ 日。ただし最長ではないため誤り。
• イ: A→D→H
  • 有効な経路で所要日数は $1+3+4=8$ 日。短いため誤り。
• ウ: B→E→F→H
  • 図中の破線矢印 F は右上中間ノードから右下中間ノードへ向かう一方向のダミー（所要日数 0）です。したがって右下中間ノード（E の到達点）から F を経て右上へ戻る経路は存在せず、この経路は成立しません（無効）。よって誤り。
• エ: B→E→G
  • 有効な経路で合計 $5+4+5=14$ 日、最長であるため正解。エ

よくある誤解

• ダミー矢印の向きを見落とし、双方向に移動できると誤認する。ダミーは向き付きの矢印であり、必ず図の向きを守る。
• ダミー作業を有時間の作業と誤って扱う（0 とすべきところを加算する）。
• 全経路を列挙せずに一部だけ比較してしまい、最長経路を見逃す。

補足コラム

• アローダイアグラム（Activity on Arrow, AOA）ではダミー矢印を使って先行関係を表現します。ダミーは所要日数が 0 で、同じノードに複数の作業が入出力するときの依存関係整理に用いられます。
• クリティカルパス法（CPM）を厳密に行うには、各作業の早始・早終・遅始・遅終を求めてスラック（余裕）を算出し、スラックが 0 の経路を特定する方法が標準です。本問は単純にパス合計で判定できるケースです。
• 図が複雑な場合は、経路列挙→合計→最大値抽出の手順を表にするか、小さなメモをノードごとに作るとミスが減ります。

FAQ