开始 → A(3) → C(4) → E(2) → 结束
     ↘ B(2) → D(3) ↗

xxx 关键路径算法（Critical Path Method） 题目描述 关键路径算法用于在项目管理的活动网络图中确定关键路径。给定一个有向无环图（DAG），顶点表示事件（如项目阶段），边表示活动（如任务），每条边有权重代表活动持续时间。我们需要找到从起点到终点的最长路径（关键路径），该路径决定了项目的最短完成时间，路径上的活动称为关键活动（延迟会导致整个项目延迟）。 解题过程 步骤1：理解问题基础 活动网络图必须是DAG，确保无循环依赖 每个活动有： 最早开始时间（ES）：所有前驱活动完成的最早时间 最晚开始时间（LS）：不延误项目的前提下最晚开始时间 松弛时间（Slack）：LS - ES，为0的活动即关键活动 步骤2：构建图结构 假设我们有一个示例项目： 活动A：耗时3，无前驱 活动B：耗时2，无前驱 活动C：耗时4，需要A完成 活动D：耗时3，需要A、B完成 活动E：耗时2，需要C、D完成 对应的DAG为： 步骤3：计算最早开始时间（正向传播） 从起点开始，按拓扑顺序计算每个顶点的最早发生时间（ET）： ET[ 开始 ] = 0 ET[ 顶点 ] = max{前驱顶点的ET + 活动时间} 计算过程： ET[ A] = ET[ 开始 ] + 0 = 0（A从时间0开始） ET[ B] = ET[ 开始 ] + 0 = 0 ET[ C] = ET[ A ] + 3 = 3 ET[ D] = max(ET[ A]+3, ET[ B ]+2) = max(3, 2) = 3 ET[ E] = max(ET[ C]+4, ET[ D ]+3) = max(7, 6) = 7 ET[ 结束] = ET[ E ] + 2 = 9 步骤4：计算最晚开始时间（反向传播） 从终点开始，按逆拓扑顺序计算每个顶点的最晚发生时间（LT）： LT[ 结束] = ET[ 结束 ] = 9（项目总时间） LT[ 顶点 ] = min{后继顶点的LT - 活动时间} 计算过程： LT[ E] = LT[ 结束 ] - 2 = 7 LT[ C] = LT[ E ] - 4 = 3 LT[ D] = LT[ E ] - 3 = 4 LT[ A] = min(LT[ C]-3, LT[ D ]-3) = min(0, 1) = 0 LT[ B] = LT[ D ] - 2 = 2 LT[ 开始] = min(LT[ A]-0, LT[ B ]-0) = 0 步骤5：识别关键路径 计算每个活动的松弛时间 = LS - ES = LT[ 终点] - ET[ 起点 ] - 活动时间： 活动A：LS=0, ES=0, 松弛=0 ✓ 活动B：LS=2, ES=0, 松弛=2 活动C：LS=3, ES=3, 松弛=0 ✓ 活动D：LS=4, ES=3, 松弛=1 活动E：LS=7, ES=7, 松弛=0 ✓ 关键路径：开始→A→C→E→结束，总时长9 算法总结 关键路径算法通过拓扑排序的正向传播计算最早时间，反向传播计算最晚时间，零松弛的活动构成关键路径。该算法时间复杂度为O(V+E)，是项目管理中进度控制的基石工具。