关键路径

　　关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。1

　　介绍

　　关键路径通常（但并非总是）是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。2但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。

　　一个项目可以有多个、并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。关键链方法中增加了资源约束。关键路径方法是由杜邦公司发明的。

　　步骤

　　A、从开始顶点 v1 出发，令 ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。3

　　Ve(k)=max{ve(j)+dut()} , j ∈ T 。其中T是以顶点vk为尾的所有弧的头顶点的集合（2 ≤ k ≤ n）。

　　如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

　　B、从完成顶点出发，令，按逆拓扑有序求其余各顶点的允许的最晚发生时间：

　　vl(j)=min{vl(k)-dut()} ,k ∈ S 。其中 S 是以顶点vj是头的所有弧的尾顶点集合（1 ≤ j ≤ n-1）。

　　C、求每一项活动ai（1 ≤ i ≤ m）的最早开始时间e(i)=ve(j)，最晚开始时间l(i)=vl(k)-dut() 。

　　若某条弧满足 e(i)=l(i) ，则它是关键活动。

　　相关术语

　　（1）AOE网

　　用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。例如：图1 是一个网。其中有9个事件v1,v2,…,v9；11项活动a1,a2,…,a11。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如 v1表示整个工程开始，v9 表示整个工程结束。V5表示活动a2和a3已经完成，活动a7和a8可以开始。与每个活动相联系的权表示完成该活动所需的时间。如活动a1需要6个时间单位可以完成。

　　一个AOE网的关键路径可以不止一条。

　　只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度过为0的开始顶点和唯一的出度为0的完成顶点。

　　（2） 活动开始的最早时间e(i)；

　　（3） 活动开始的最晚时间l(i) 定义e(i)=l(i）的活动叫关键活动；

　　（4） 事件开始的最早时间ve(i)；

　　（5） 事件开始的最晚时间vl(i)。

　　应用

　　（1） 完成整个工程至少需要多少时间；

　　（2） 哪些活动是影响工程的关键。

　　1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。

　　算法

　　（1） 输入e条弧，建立AOE网的存储结构；

　　（2） 从源点v1出发，令ve(1)=0，求 ve(j) ,2ve[k]) ve[k]=ve[j]+*(p->info);

　　}

　　}

　　if(countnextarc)

　　{k=p->adjvex; dut=*(p->info);

　　if(vl[k]-dutadjvex; dut=*(p->info);

　　ee=ve[j]; el=vl[k];

　　tag=(ee==el)?’*’：’’；

　　printf(j,kdut,ee,el,tag);

　　}

　　}4

　　C++完整代码

　　#include

　　#include

　　#include

　　using namespace std;

　　int n,m,w[1001][1001],prev[1001],queue[1001],Time[1001],l=0,r=0,Pos[1001],path[1001];

　　void init()

　　{

　　int i,a,b,c;

　　scanf("%d%d",&n,&m);

　　for (i=1;i