关键路径法 (CPM)

关键路径法（CPM）在项目网络中找出最长的一串相互依赖的活动，它决定了项目的最短工期。位于该关键路径上的活动没有浮动时间：它们的任何延误都会拖延整个项目。

工作原理

项目被建模为带工期的活动有向无环图。按拓扑顺序的前向遍历计算每个活动的最早开始与结束；后向遍历计算不拖延项目的最晚时间。最晚开始与最早开始之差是活动的浮动时间，浮动为零的活动构成关键路径。两次遍历都运行在 O(V + E)。

应用场景

CPM 为建筑工程、软件发布、制造换型和活动策划排程。Primavera 和 Microsoft Project 等项目管理工具持续计算关键路径。它也是 DAG 中最长路径和拓扑排序的教科书应用。