Critical path scheduling

The longest chain of dependent tasks sets the floor on how fast everything can finish — speeding up anything else changes nothing.

The idea

Picture a project as a graph of tasks. Some tasks can't start until others are done: you can't paint a wall before it's built. Each task takes some time. Lay the dependencies out as arrows and you get a directed acyclic graph (DAG) — arrows only point forward, never in a loop.

The whole project can't finish until its slowest chain of dependencies is done. That chain — the critical path — is the longest weighted path through the DAG. Its length is the minimum possible finish time. Every task on it has zero slack: delay one and the whole project slips. Tasks off the path have spare room, so rushing them buys you nothing.

See it work

Press play to topologically order the tasks, run the forward pass, then light up the critical path.

How it works

Process nodes in topological order so every predecessor is computed before the node that needs it. Each task's earliest finish is its own duration plus the latest of its predecessors' finishes — max over preds, not sum. The project finish is the largest finish of all. A backward pass gives each task a latest finish; slack = LF − EF, and the zero-slack chain is the critical path.

for v in topo_order(G):                       # preds done first
    EF[v] = dur[v] + max([EF[u] for u in preds[v]], default=0)

finish = max(EF.values())                     # project finish time

# backward pass for slack
for v in reverse(topo_order(G)):
    LF[v]    = min([LF[w] - dur[w] for w in succs[v]], default=finish)
    slack[v] = LF[v] - EF[v]

# critical path = the chain of tasks where slack == 0

Cost

Operation	Cost	Why
Topological sort	O(V + E)	Visit each task and each dependency edge once
Forward + backward pass	O(V + E)	One DP sweep over the sorted order; each edge relaxed once
Whole critical path	O(V + E)	Longest path on a DAG is linear — the topo order removes the hard cases
Brute-force longest path	exponential	Enumerating every source-to-sink path explodes; on a general graph longest path is NP-hard

Watch out for

A cycle makes it ill-defined. If task X waits on Y and Y waits on X, there's no valid finish time and no topological order. The input must be a DAG — detect cycles before you run the passes.
Summing predecessors instead of taking the max. A task is ready when its last prerequisite finishes, not when all of them added together would. Use max over predecessor finishes, never a sum.
Crashing a non-critical task to go faster. Speeding up a task with positive slack changes nothing — the critical path still sets the floor. Shorten a task on the path, then re-check, because the critical path can shift.
Confusing total slack with free slack. Total slack is room before the project slips; free slack is room before a successor slips. Spending total slack can still delay the next task downstream.
Treating CPM as a schedule with limited workers. The critical path assumes tasks run in parallel whenever dependencies allow. Real resource limits (one machine, one engineer) can stretch the finish beyond the path length.

Worked example

Six tasks with durations and dependencies. A(3) starts the project; B(2) and C(4) both need A; D(4) needs both B and C; E(3) needs C; F(2) needs both D and E. Run the forward pass in topological order: EF_A = 3, EF_B = 3 + 2 = 5, EF_C = 3 + 4 = 7, EF_D = max(EF_B=5, EF_C=7) + 4 = 11, EF_E = 7 + 3 = 10, EF_F = max(EF_D=11, EF_E=10) + 2 = 13. The project finishes at 13. Backtracking the zero-slack chain gives A → C → D → F. B has 2 units of slack and E has 1 — you could start either late without slipping the project.

The interactive graph above is a 7-task variant (it adds a final task G); the logic and the readout are identical.

Check yourself

In the worked example, task B has 2 units of slack. If your team finds a way to finish B one day faster, what happens to the project finish time of 13?

Coach note: if this didn't click yet, replay the visual and watch which nodes stay lit at the end. Only those — the zero-slack chain — move the finish line when you change them.