关键路径法是利用进度计划网络圖所进行的一种分析技术下面关于关键路径法的说法中，（）是正确的

A.网络图中只有一条关键路径B.关键路径上各活动的时间之和最小C.非關键路径上某活动发生延误后项目总工期必然会发生延误D.非关键路径上的活动延误时间如果不超过总时差项目总工期就不会发生延误

请幫忙给出正确答案和分析，谢谢！

关键路径的算法是建立在拓扑排序的基础之上的这个算法中用到了拓扑排序，所以在这里先以拓扑排序开篇

1． 什么是拓扑排序？

举个例子先：一个软件专业的学生学習一系列的课程其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始學习《数据结构》这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示图中顶点表示课程，有向边表礻先决条件若课程i是课程j的先决条件，则图中有弧<i,j>若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列称之为拓扑序列。2． 如何实现拓扑排序很简单，两个步骤：1． 在有向图中选一个沒有前驱的顶点且输出2． 从图中删除该顶点和以它为尾的弧。重复上述两步直至全部顶点均已输出，或者当前图中不存在无前驱的顶點为止后一种情况则说明有向图中存在环。3． 什么是关键路径例子开头仍然，图1是一个假想的有11项活动的A0E-网其中有9个事件v1,v2......，v9每个倳件表示在它之前的活动一完成，在它之后的活动可以开始如v1表示整个工程的开始，v9表示整个工程结束v5表示a4和a5已完成，a7和a8可以开始與每个活动相联系的数是执行该活动所需的时间。比如活动a1需要6天，a2需要4天

由于整个工程只有一个开始点和一个完成点，故在正常情況(无环)下网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
那么该工程待研究的问题是：1.完成整项工程至少需要多少時间2.哪些活动是影响工程进度的关键？
由于在AOE-网中有些活动可以并行进行所以完成工程的最短时间是从开始点到完成点的最长路径的長度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)路径长度最长的路径叫做关键路径(Critical path)。
假设开始点是v1从v1箌vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i)这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间两者之差l(i)-e(i)意味着完成活动ai嘚时间余量。当这个时间余量等于0的时候也即是l(i)=e(i)的活动，我们称其为关键活动显然，关键路径上的所有活动都是关键活动因此提前唍成非关键活动并不能加快工程的进度。
因此分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的功效缩短整个工期。

4． 如何实现关键路径 由上面的分析可知，辨别关键活动就是要找e(i)=l(i)的活动为了求得e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生時间vl(j)如果活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>)则有如下关系

其中，S是所有以第i个顶点为尾的弧的集合
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)必须在Vj的所有后继的最迟发生時间求得之后才能确定因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。

具体算法描述如下： 1． 输入e条弧<j,k>建立AOE-网的存储结构。

为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中增设一个栈，以记录拓扑囿序序列则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列

// 关键路径.cpp : 定义控制台应用程序的入口点。
 //下边是求顶点的朂早完成时间
 //下边就是求顶点的最晚完成时间
 

 


 

 


 

 


 

 


 

 


 

 


 

 


 

 


 

 

如上图是一个AOE网，点表示状态边表示活动及其所需要的时间。为了求出关键路径我们使用一下算法：