計算問題の解き方・2/20
アローダイアグラムのクリティカルパス（最長経路）の求め方
作業名と所要日数を書いたアローダイアグラムが示され、プロジェクト完了までの最少（最短）所要日数、クリティカルパス、ある結合点の最早結合点時刻、作業を短縮したときに全体が何日縮むかが問われます。どの聞き方でも、開始から終了までの経路のうち所要日数がいちばん長い経路を見つけることが土台になります。
公開過去問での出題：本試験系 19 回・免除試験 51 回（観測値）
覚える式
- 最早結合点時刻 ＝ max（直前の結合点の最早結合点時刻 ＋ その間の作業の所要日数）※ダミー作業は 0 日
- プロジェクトの最少所要日数 ＝ 終了結合点の最早結合点時刻 ＝ 最長経路（クリティカルパス）の日数
解き方の手順
- 結合点に左から番号を振り、開始の結合点の最早結合点時刻を 0 とします。
- 左から順に、各結合点へ入ってくる矢印すべてについて「元の結合点の最早結合点時刻＋作業日数」を計算し、その最大値をその結合点の最早結合点時刻として書き込みます。入ってくる矢印が複数あるときは、すべての計算が終わってから最大値を決めます。
- ダミー作業（破線矢印）は所要日数 0 日の作業として扱い、元の結合点の時刻をそのまま矢印の先へ渡します。ダミーを飛ばすと経路を 1 本見落とします。
- 終了結合点の最早結合点時刻が、プロジェクト完了までの最少所要日数です。
- クリティカルパスを聞かれたら、終了結合点から逆にたどり、最大値を決めた矢印（最大値を出した側）を選んでいくと最長経路の作業の並びが分かります。
- 作業の短縮を聞かれたら、短縮後の日数で手順 2〜4 をやり直し、短縮前の日数との差を求めます。
例題
アローダイアグラムの日程計画をもつプロジェクトの，開始から終了までの最少所要日数は何日か。
アローダイアグラム（凡例: ○─作業名／所要日数→○）。結合点を左から n0（開始）, n1, n2, n3, n4, n5, n6, n7, n8（終了）とすると:
n0 →A(2)→ n1
n1 →B(2)→ n2 →E(2)→ n3 →H(2)→ n6
n1 →C(1)→ n4 →F(3)→ n5 →I(1)→ n6
n1 →D(4)→ n7 →G(3)→ n8
n6 →J(4)→ n8
ア 9
イ 10
ウ 11
エ 12
出典：平成31年度 春期 基本情報技術者試験 午前 問53（解き方は当サイト作成）
解き方と答えを見る
- 開始 n0 の最早結合点時刻 ＝ 0 日
- n1 ＝ 0＋A(2) ＝ 2 日
- n2 ＝ 2＋B(2) ＝ 4 日、n3 ＝ 4＋E(2) ＝ 6 日
- n4 ＝ 2＋C(1) ＝ 3 日、n5 ＝ 3＋F(3) ＝ 6 日
- n6 ＝ max（n3 から H：6＋2 ＝ 8、n5 から I：6＋1 ＝ 7）＝ 8 日
- n7 ＝ 2＋D(4) ＝ 6 日
- 終了 n8 ＝ max（n7 から G：6＋3 ＝ 9、n6 から J：8＋4 ＝ 12）＝ 12 日
- 逆にたどると J←H←E←B←A。クリティカルパスは A→B→E→H→J で 2＋2＋2＋2＋4 ＝ 12 日です。
答え：12日（エ）
ひっかけ
- 「最少」「最短で何日」という聞き方につられて、いちばん短い経路の日数を選んでしまう誤りです。どの作業もすべて終わらないとプロジェクトは完了しないので、答えは最長経路の日数です。例題では最短経路 A→D→G の 9 日（ア）がこの誤答になります。
- ダミー作業を無視して、破線でつながる経路を数え忘れる誤りです。ダミーは 0 日でも「この結合点の作業が終わってから次へ進む」という順序の制約なので、ダミーを通る経路も必ず候補に入れます。
- 結合点に複数の矢印が入るとき、最初に計算した値や小さい方の値をその結合点の時刻にしてしまう誤りです。必ず入ってくる矢印すべてを計算してから最大値を取ります。
- クリティカルパス上の作業を縮めれば、縮めた日数だけ全体も縮むと考える誤りです。縮めた結果、別の経路のほうが長くなると、全体はその経路の日数までしか縮みません。短縮後の日数で最早結合点時刻を計算し直して確かめます。
類題（手順を使って解く）
類題 1
ダミー作業が 2 本続く図で、ダミーを 0 日の作業として時刻を受け渡し、ダミーを通る経路まで含めて最大値を取れるかが試されます。
アローダイアグラムで表されるプロジェクトは，完了までに最少で何日を要するか。
アローダイアグラム（矢印の上に作業名，下に所要日数。破線矢印はダミー作業）
結合点: s(開始), n1, n2(上), n3(中), n4(下), n5, 終了
s → n1: A(30)
n1 → n2: B(5)
n1 → n3: C(30)
n1 → n4: D(20)
n2 → n5: E(40)
n3 → n5: F(25)
n4 → n5: G(30)
n5 → 終了: H(30)
ダミー作業（破線）: n2 → n3, n3 → n4
出典：令和6年度 基本情報技術者試験 科目A 公開問題 問13（問題文は IPA の公開問題。答えと解説はリンク先）
類題 2
日数ではなくクリティカルパスの作業の並びを答える問題で、ダミーを含めて最早結合点時刻を求めたあと、終了から逆にたどって最大値を出した矢印を選べるかが試されます。
あるプロジェクトの日程計画をアローダイアグラムで示す。クリティカルパスはどれか。
アローダイアグラム（凡例: ○—作業名/所要日数→○，破線矢印はダミー作業）。結合点を N1〜N6 とすると:
A: N1→N2（1日）
B: N1→N3（5日）
C: N2→N3（3日）
D: N2→N5（3日）
E: N3→N4（4日）
ダミー: N4→N5（破線）
F: N4→N6（5日）
G: N5→N6（4日）
出典：令和元年度 秋期 基本情報技術者試験 午前 問52（問題文は IPA の公開問題。答えと解説はリンク先）
類題 3
作業を 1 日ずつ短縮する組合せを比べる問題で、候補ごとに短縮後の日数で計算し直し、2 番目に長い経路も含めて全体が本当に 2 日縮むかを確かめられるかが試されます。
図のアローダイアグラムにおいて，プロジェクト全体の期間を短縮するために，作業 A～E の幾つかを 1 日ずつ短縮する。プロジェクト全体の期間を 2 日短縮できる作業の組みはどれか。
アローダイアグラム（ノード N1〜N5）: N1→N2 作業 A（6 日），N1→N3 作業 B（3 日），N3→N2 作業 C（4 日），N2→N5 作業 D（2 日），N3→N4 作業 E（4 日），N4→N5 作業 F（1 日）。凡例: 丸（結合点）の間の矢印に作業名と所要日数。
出典：平成30年度 春期 基本情報技術者試験 午前 問51（問題文は IPA の公開問題。答えと解説はリンク先）