D1 4.3 - Finding the critical path | Edexcel A-Level Further Mathematics

Use forward and backward passes to calculate event times, activity start and finish times, and every critical path. You will also calculate a lower bound for the workers needed to meet the minimum project duration.

A project must wait for its longest dependency chain

Can a one-hour activity join two fixed-time events without being critical? In this project, $H$ joins an event fixed at hour $4$ to the finish fixed at hour $12$ . Its one hour of work leaves room to move. Identifying critical work needs the activity's duration as well as its endpoint event times.

You already know

Activities are directed arcs and events wait for every incoming activity. A dummy is a zero-duration directed dependency. Recall the project network from D1 4.1, 4.2; each real activity below has its duration in hours.

The network and duration table define the project used throughout this lesson.

Activity	Start event	Finish event	Duration, hours
$A$	$1$	$2$	$4$
$B$	$1$	$3$	$3$
Dummy	$2$	$3$	$0$
$C$	$2$	$4$	$5$
$D$	$3$	$4$	$2$
$E$	$3$	$5$	$4$
$F$	$4$	$6$	$3$
$G$	$5$	$6$	$2$
$H$	$2$	$6$	$1$

[DIAGRAM: asset_name: Activity network with project durations; asset_slug: 9fm0-d1173-duration-network; caption: Arc brackets give durations in hours, while the dashed dummy has duration zero; description: The six-event network from the preceding lesson is redrawn with activity durations A(4), B(3), C(5), D(2), E(4), F(3), G(2), H(1). H follows a high curved route from event 2 to event 6. A dashed arrow from event 2 to event 3 represents the zero-duration dummy. All arrows and labels are clear, and numbers inside circles identify events.]
Arc brackets give durations in hours, while the dashed dummy has duration zero

A directed start-to-finish path lists activities that must happen in sequence, so the project cannot finish sooner than that path's total duration. With sufficient resources, the longest such path determines the minimum completion time. This assumes the stated dependencies and fixed durations are the only restrictions; a limited workforce can impose a later finish.

Early and late event times

The early event time $E_i$ is the earliest time event $i$ can occur. The late event time $L_i$ is the latest it can occur without delaying the chosen project finish.

Use time $0$ at the start. For the minimum-duration analysis, the late finish time is set equal to the earliest finish time.

An early time is an “all prerequisites ready” time, so a merge uses the greatest incoming completion. A late time must protect every successor, so it uses the smallest outgoing allowance.

Key idea

First find the earliest possible finish without resource restrictions. Then work backwards from that same finish to identify how late each event may occur.

Check which chain controls the time lower bound.

Forward pass: take the maximum at every merge

Work in an order where every event's incoming tails have already been processed. Add each incoming activity duration to its tail's early time, then take the largest arrival.

Forward-pass algorithm

For an arc $i\to j$ of duration $d_{ij}$ ,

E_{\mathrm{start}}=0,\qquad E_j=\max_{i\to j}(E_i+d_{ij})

A dummy contributes duration $0$ , but its incoming arrival must still be considered.

Not in the formula booklet: learn it.

The maximum ensures the event waits for every prerequisite, including one carried by a dummy.

Worked example 1: the original forward pass

Question. Calculate all early event times for the pictured project.

Plan. Start with event $1$ , then evaluate all incoming arrivals at each later event.

\begin{aligned} E_1&=0 && \text{start}\\ E_2&=0+4=4 && A\\ E_3&=\max(0+3,4+0)=4 && B,\text{ dummy}\\ E_4&=\max(4+5,4+2)=9 && C,D\\ E_5&=4+4=8 && E\\ E_6&=\max(9+3,8+2,4+1)=12 && F,G,H \end{aligned}

Why this step? At event $3$ , $B$ finishes at hour $3$ , but the dummy carries the requirement to wait until $A$ finishes at hour $4$ .

Answer. $(E_1,E_2,E_3,E_4,E_5,E_6)=(0,4,4,9,8,12)$ ; minimum completion time $12$ hours.

Check. Path $A,C,F$ takes $4+5+3=12$ hours, so the project cannot finish earlier.

Change only $B$ 's duration from $3$ hours to $6$ hours. The later arrival at its merge can now control another branch.

Worked example 2: a changed incoming maximum

Question. Recalculate the early event times when $B$ takes $6$ hours.

Plan. Keep $E_2$ , update the merge at event $3$ , then propagate that change.

\begin{aligned} E_1&=0,\qquad E_2=4 && \text{unchanged}\\ E_3&=\max(6,4)=6 && \text{new }B\text{ duration}\\ E_4&=\max(4+5,6+2)=9 && C,D\\ E_5&=6+4=10 && E\\ E_6&=\max(9+3,10+2,4+1)=12 && \text{two tied arrivals} \end{aligned}

Why this step? A change need not affect every downstream early time. Event $4$ still waits for the longer $C$ branch, while event $5$ moves later.

Answer. Early times $(0,4,6,9,10,12)$ ; minimum project duration remains $12$ hours.

Check. Both $A,C,F$ and $B,E,G$ now have duration $12$ .

All subsequent examples return to the original durations unless a change is explicitly stated.

Watch out

Wrong: average the arrival times at a merge or choose the smallest. Right: the event cannot happen before its last prerequisite finishes, so take the maximum.

Make a smaller change to the same incoming activity.

Backward pass: protect every successor with a minimum

Fix the project finish at its earliest time. Work backwards, subtracting each outgoing duration from the late time at its head. Choose the smallest allowance, because all outgoing activities must still fit.

Backward-pass algorithm

L_{\mathrm{finish}}=E_{\mathrm{finish}},\qquad L_i=\min_{i\to j}(L_j-d_{ij})

In Pearson's stacked event boxes, write the early event time in the top box and the late event time in the bottom box.

Not in the formula booklet: learn it.

The small event labels in the diagrams identify which box is being discussed; they are not extra times.

Worked example 3: the original backward pass

Question. Find every late event time for the original project, finishing at hour $12$ .

Plan. Start at event $6$ and work backwards through every outgoing arc.

\begin{aligned} L_6&=12 && \text{fixed finish}\\ L_4&=12-3=9,\qquad L_5=12-2=10 && F,G\\ L_3&=\min(9-2,10-4)=6 && D,E\\ L_2&=\min(9-5,6-0,12-1)=4 && C,\text{ dummy},H\\ L_1&=\min(4-4,6-3)=0 && A,B \end{aligned}

Why this step? At event $3$ , choosing $7$ instead of $6$ would let $E$ finish after its permitted event- $5$ time of $10$ .

Answer. $(L_1,L_2,L_3,L_4,L_5,L_6)=(0,4,6,9,10,12)$ .

Check. Every late time is at least its early time, and the start remains at $0$ , consistent with a minimum-duration finish.

Change only $D$ 's duration from $2$ to $5$ hours. Its early arrival ties $C$ 's at event $4$ , so all early event times and the $12$ -hour finish stay unchanged.

Worked example 4: a tighter outgoing allowance

Question. Find the late event times with $D$ taking $5$ hours and the project still finishing at hour $12$ .

Plan. Recompute the allowance along $D$ , then continue backwards.

\begin{aligned} L_6&=12,\quad L_4=9,\quad L_5=10 && \text{unchanged successor durations}\\ L_3&=\min(9-5,10-4)=4 && \text{changed allowance}\\ L_2&=\min(9-5,4-0,12-1)=4 && \text{include the dummy}\\ L_1&=\min(4-4,4-3)=0 && \text{start} \end{aligned}

Why this step? A longer activity can tighten a late event time even when no early time changes. The early and late passes answer different questions.

Answer. Late times $(0,4,4,9,10,12)$ .

Check. Event $3$ must now occur at hour $4$ , leaving exactly $5$ hours for $D$ to reach event $4$ at hour $9$ .

[DIAGRAM: asset_name: Early and late event boxes for the original project; asset_slug: 9fm0-d1173-original-times; caption: Early times are above late times; the original critical route is A, C, F; description: The project network has two stacked boxes at each event, with early times 0,4,4,9,8,12 above late times 0,4,6,9,10,12 for events 1 to 6. Every real arc is labelled with its original duration and every arc has an arrowhead. A, C and F are blue. The dashed dummy from event 2 to 3 is not critical. Small event identifiers sit outside the timing boxes, and the diagram key states top equals early, bottom equals late.]
Early times are above late times

The displayed boxes return to the original $D=2$ project, ready for the activity calculations that follow.

Watch out

Wrong: take a backward maximum because the forward pass used a maximum. Right: take a minimum, protecting the earliest deadline among all outgoing requirements.

Change $D$ 's duration to a value between the two worked examples.

Event times give four activity times

An activity can start when its tail event first occurs. To finish as late as allowed without delaying the project, it must reach its head event by that event's late time.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D1 4.3 - Finding the critical path

A project must wait for its longest dependency chain

Forward pass: take the maximum at every merge

Backward pass: protect every successor with a minimum

Event times give four activity times

Continue this lesson.

Learn faster with Nova