Interactive Graph Theory Learning
Interactive Graph Theory Learning
Guest User
Using app without sign in
Critical path calculator
Identifies the longest sequence of dependent tasks in a project schedule, determining the shortest time possible to complete the project.
Select an algorithm and generate steps to begin visualization
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.
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).
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.
Read the full article: Operations Research and Graph Theory
Related algorithms: PERT (Program Evaluation and Review Technique), RCPSP (Resource-Constrained Project Scheduling), Topological Sort