This algorithm requires a directed graph. Check Settings tab to configure.
Critical Path Method (CPM)
Identifies the longest sequence of dependent tasks in a project schedule, determining the shortest time possible to complete the project.
Time: O(V + E)
Space: O(V)
Use Case: Project scheduling and bottleneck identification.
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Critical Path Method (CPM)
The Critical Path Method (CPM) finds the longest chain of dependent activities in a project network, which determines the minimum project duration. Activities on this critical path have zero slack: any delay in them delays the whole project.
How it works
The project is modeled as a directed acyclic graph of activities with durations. A forward pass in topological order computes the earliest start and finish of each activity; a backward pass computes the latest times that avoid delaying the project. The difference between latest and earliest start is the activity's float, and activities with zero float form the critical path. Both passes run in O(V + E).
Applications
CPM schedules construction projects, software releases, manufacturing changeovers, and event planning. Project management tools such as Primavera and Microsoft Project compute critical paths continuously. It is also a textbook application of longest paths in DAGs and topological sorting.