Critical Path Calculator

Pseudocode

Two sweeps over the activity network in topological order: forward for the earliest each task can happen, backward for the latest it can happen without delaying the project.

CPM(activities, dependencies):
    order = topologicalSort(activities)

    // Forward pass: earliest start and finish
    for each activity a in order:
        ES[a] = max(EF[p] for p in predecessors(a)), or 0
        EF[a] = ES[a] + duration[a]
    T = max(EF[a] for all a)      // project duration

    // Backward pass: latest start and finish
    for each activity a in reverse(order):
        LF[a] = min(LS[s] for s in successors(a)), or T
        LS[a] = LF[a] - duration[a]

    slack[a] = LS[a] - ES[a]
    critical path = activities with slack 0

The critical path is the longest path through the network, not the shortest, which is what makes this a maximisation problem on a DAG rather than a shortest-path one. Because the network is acyclic, both sweeps are just dynamic programming in topological order and no priority queue is needed. Slack of zero means the activity has nowhere to move: delay it by a day and the whole project slips by a day.

Worked example, step by step

Schedule a four-activity project where two tasks can run in parallel but both must finish before the third begins.

Example graph: Activities with durations A (3 days), B (2 days), C (4 days) and D (2 days). Dependencies: A and B must both precede C, and C precedes D.

1. Forward pass, A and B. Neither has a predecessor, so both start at time 0. A finishes at 3, B finishes at 2. They run in parallel.
2. Forward pass, C. C waits for both, so its earliest start is the maximum of 3 and 2, which is 3. It runs 4 days and finishes at 7. Note that B finished a day earlier and simply waits.
3. Forward pass, D. D starts at 7 and finishes at 9. Nothing follows it, so the project duration is 9 days.
4. Backward pass. Working back from 9: D must start by 7, so C must finish by 7 and start by 3. Both A and B must therefore finish by 3, giving A a latest start of 0 and B a latest start of 1.
5. Compute slack. A has latest start 0 against earliest start 0, so slack 0. B has latest start 1 against earliest start 0, so slack 1. C and D both have slack 0.

The project takes 9 days and the critical path is A to C to D. B has one day of float, meaning it can start a day late or overrun by a day without affecting the finish date. This is the practical payoff: it tells a manager exactly where to concentrate attention. Shortening B is worthless, while shortening any of A, C or D shortens the whole project, at least until the critical path shifts to run through B instead.

Complexity, and where it comes from

Time: O(V + E) · Space: O(V)

A topological sort costs O(V + E), and each of the two sweeps visits every activity once and every dependency edge once, so both are O(V + E) as well. Space is four numbers per activity, the earliest and latest start and finish, so O(V). The whole method is linear, which is why it scales to project networks with hundreds of thousands of activities. The dependency network must be a directed acyclic graph: a circular dependency has no topological order, and correspondingly no valid schedule, so cycle detection is a genuine prerequisite rather than a formality.

When to use Critical Path Method (CPM), and when not to

CPM assumes durations are known and resources unlimited. Relaxing either assumption changes the problem.

Common pitfalls

• Taking the minimum instead of the maximum in the forward pass. An activity cannot start until every predecessor is done, so the earliest start is the maximum over predecessor finishes. Using the minimum produces a schedule that is impossibly short and quietly wrong.
• Assuming the critical path is unique. Several paths can tie for longest, and then every activity on all of them has zero slack. Shortening just one does nothing, because the other critical path still governs the finish date.
• Forgetting that the critical path moves. Shorten a critical activity enough and a different path becomes the longest. Crashing must be re-evaluated after each change rather than applied all at once from the original analysis.
• Ignoring resource limits. CPM assumes A and B really can run at the same time. If both need the same machine or the same person, the schedule is fiction and you need RCPSP instead.
• Running it on a network with a cycle. A circular dependency means no topological order exists and no schedule is valid. Detect the cycle and report it rather than producing numbers from a partial order.

Frequently asked questions

What is the critical path method?

CPM finds the longest path through a project network of activities and dependencies, which determines the shortest possible project duration. Activities on that path have zero slack, meaning any delay to them delays the entire project. It is computed with a forward pass for earliest times and a backward pass for latest times.

What is slack or float in CPM?

Slack is the amount of time an activity can be delayed without pushing back the project finish, calculated as latest start minus earliest start. Activities with zero slack are critical. In the worked example above, activity B has one day of slack while A, C and D have none.

What is the time complexity of the critical path method?

O(V + E), where V is the number of activities and E the number of dependencies. It is a topological sort followed by two linear sweeps over the network, so it scales easily to very large project plans.

What is the difference between CPM and PERT?

CPM uses a single deterministic duration per activity and focuses on identifying the critical path and float. PERT uses three estimates per activity, optimistic, most likely and pessimistic, to compute an expected duration and a variance, which lets you state the probability of finishing by a given date. The network analysis itself is the same.

Can the critical path change during a project?

Yes, and this is the main practical trap. If a critical activity is shortened or a non-critical one overruns its float, a different path can become the longest. The analysis must be rerun as actual durations become known rather than treated as fixed at planning time.