关键路径
出自 MBA智库百科(https://wiki.mbalib.com/)
关键路径（Critical Path）
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。
目录 |
在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。
关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。
一个项目可以有多个，并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。
最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。
关键路径方法是由杜邦公司发明的。
关键路线具有以下特点：
1、关键路线上的活动的持续时间决定项目的工期，关键路线上所有活动的持续时间加起来就是项目的工期。
2、关键路线上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完成时间的延迟。
3、关键路线是从始点到终点的项目路线中耗时最长的路线，因此要想缩短项目的工期，必须在关键路线上想办法，反之，若关键路线耗时延长，则整个项目的完工期就会延长。
4、关键路线的耗时是可以完成项目的最短的时间量。
5、关键路线上的活动是总时差最小的活动。
探寻关键路径[1]
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。例如：
图1 是一个网。其中有9个事件v1，v2，…，v9；11项活动a1，a2，…，a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动，a4和a5已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6天时间可以完成。
1)AOV 网具有的性质
- 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
- 只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。
- 表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。
2)由事件vj的最早发生时间和最晚发生时间的定义，可以采取如下步骤求得关键活动：
A、从开始顶点 v 1 出发 , 令 ve(1)=0, 按拓朴有序序列求其余各顶点的可能最早发生时间。
- Ve(k)=max{ve(j)+dut(<j,k>)} （ 1.1 ）
- j ∈ T
其中T是以顶点vk为尾的所有弧的头顶点的集合(2 ≤ k ≤ n) 。
如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。
B、从完成顶点 v n 出发，令vl(n)=ve(n)，按逆拓朴有序求其余各顶点的允许的最晚发生时间:
- vl(j)=min{vl(k)-dut(<j,k>)}
- k ∈ S
其中 S 是以顶点vj是头的所有弧的尾顶点集合(1 ≤ j ≤ n-1) 。
C、求每一项活动ai(1 ≤ i ≤ m)的最早开始时间e(i)=ve(j)；最晚开始时间：
- l(i)=vl(k)-dut(<j,k>)
若某条弧满足 e(i)=l(i) ，则它是关键活动。
对于图1所示的 AOE 网，按以上步骤的计算结果见表1，可得到a1 , a4 , a7 , a8 , a10 , a11 是关键活动。
3）求出 AOE 网中所有关键活动后，只要删去AOE网中所有的非关键活动，即可得到 AOE 网的关键路径。
这时从开始顶点到达完成顶点的所有路径都是关键路径。一个AOE网的关键路径可以不止一条，如图7.21的AOE网中有二条关键路径，(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它们的路径长度都是16 。如图2所示：
注意:并不是加快任何一个关键活动都可以缩短整个工程完成的时间，只有加快那些包括在所有的关键路径上的关键活动才能达到这个目的。只有在不改变AOE网的关键路径的前提下，加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间。
- ↑ 杨秀金,张红梅.数据结构(第二版).西安电子科技大学出版社.2006
Very clear.