xxx 关键路径算法（Critical Path Method）

题目描述
在带权有向无环图（DAG）中，每条边代表一个任务，边权表示任务耗时。某些任务需在其他任务完成后才能开始。求从起点到终点的最长路径（即关键路径），并确定哪些任务延迟会导致整体项目延期。

解题步骤

1. 拓扑排序

   • 对DAG进行拓扑排序，得到顶点线性序列，确保所有边从左向右指向。
     示例：若任务A需在任务C之前完成，则序列中A必在C左侧。

2. 计算最早开始时间（ES）

   • 初始化起点的ES=0，按拓扑顺序遍历每个顶点u：
     • 对u的每个邻居v，更新 ES[v] = max(ES[v], ES[u] + weight(u→v))。
   • 终点的ES值即为项目最短总工期。

3. 计算最晚开始时间（LS）

   • 初始化终点的LS=ES[终点]，按逆拓扑顺序遍历每个顶点v：
     • 对v的每个前驱u，更新 LS[u] = min(LS[u], LS[v] - weight(u→v))。
   • 确保任务不延误整体工期。

4. 确定关键路径

   • 对于边u→v，若 ES[u] + weight(u→v) = LS[v]，则该边为关键任务。
   • 所有关键任务构成的路径即为关键路径（可能有多条）。

实例演示
假设DAG如下（边权为耗时）：

A→B (3), A→C (2), B→D (4), C→D (1), D→E (5)

• 拓扑排序：A, B, C, D, E
• ES计算：
  ES[A]=0 → ES[B]=3, ES[C]=2 → ES[D]=max(3+4, 2+1)=7 → ES[E]=12
• LS计算（从E倒推）：
  LS[E]=12 → LS[D]=7 → LS[B]=3, LS[C]=6 → LS[A]=0
• 关键边：A→B（0+3=LS[B]=3），B→D（3+4=LS[D]=7），D→E（7+5=LS[E]=12）
• 关键路径：A→B→D→E（总工期12）