Overview
The Critical Path Method models activities as a dependency graph with durations. Forward and backward passes compute earliest and latest times, exposing tasks with zero slack that directly control the finish date.
CoreSource checked
Critical Path Method
Finds the longest dependency path that determines a project's minimum completion time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Scheduling
- Difficulty
- Intermediate
- Family
- Dependency Scheduling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- CPM
Core Concepts
task orderingacyclic dependency orderdependency timingdependency schedulingready queuetask priorityresource allocation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use when activity durations and dependencies are known or estimated.
- Use when the main question is project completion time and critical tasks.
When Not to Use
- Avoid when resource constraints dominate the schedule but are not modeled.
- Avoid when durations are too uncertain for deterministic critical-path analysis.
What It Does
- Builds a dependency graph of project activities
- Computes earliest and latest start or finish times
- Identifies zero-slack critical activities
Use Cases
- Project planning with precedence constraints
- Build, workflow, and construction scheduling
- Finding tasks where delay changes the whole project finish time
Inputs
- Tasks
- Durations
- Dependency graph
Outputs
- Critical path
- Earliest and latest times
Key Formulas (1)
Earliest finish
earlyfinish = earlystart + duration
early_finish = early_start + durationPropagates task timing through dependency paths.
Pseudocode
- 1.Build a DAG whose nodes are activities with durations
- 2.Topologically order the activities
- 3.Run a forward pass to compute earliest start and finish times
- 4.Run a backward pass to compute latest start and finish times
- 5.Compute slack and mark zero-slack activities as critical
Canonical Example
- Input
- A(3) before B(2) and C(4); B and C before D(1)
- Output
- critical path = A, C, D with duration 8
- Explanation
- The A-C-D chain is longer than A-B-D, so delays on it delay the project.
Implementation Notes
- Topologically sort the activity graph before the forward pass.
- Use a backward pass from the project finish time to compute latest times.
- Report slack values, not only the critical path.
Common Pitfalls
- Cycles in the dependency graph make the schedule invalid.
- Ignoring resource limits can make the critical path look feasible when it is not.
- Confusing free slack and total slack leads to bad delay decisions.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow a dependency graph with the longest duration path highlighted.
Step 1 of 5: Build a DAG whose nodes are activities with durations
critical-path-graphNotes
Critical-path analysis is a dependency-duration model; resource leveling is a separate scheduling problem.
Sources (1)
What each reference supports for this entry.
Scheduling: Theory, Algorithms, and Systems
BookScheduling reference for Critical Path Method precedence, due-date, lateness, or project-schedule optimization.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesTopological Sort
Critical Path Method uses topological order on the activity DAG.
Conceptual neighborEarliest Start Time
Earliest-start computations are part of the CPM forward pass.
Related Algorithms
Tags
SchedulingDirected Acyclic GraphTask Scheduling