C语言中的关键路径算法

上一篇文章中所讨论的拓扑排序方法，其主要目的是判断一项工程是否能够按照预定计划顺利实施。然而，在某些情况下，我们还需要进一步探讨如何在最短时间内完成整个工程的问题。

在用于描述工程流程的带权有向图中，顶点被用来表示特定的事件，而有向边则代表具体的活动。边所携带的权重则对应于该活动所需的持续时间。这种以边表示活动的有向图结构被称为AOE网（Activity On Edge Network）。

AOE网具备一个显著特征：当某个顶点所代表的事件发生后，从该顶点出发的所有相关活动才具备开始执行的前提条件。同时，只有当所有指向某一顶点的活动均已完成时，该顶点所对应的事件才有可能发生。

将路径中各活动持续时间相加所得的结果称为路径长度。而在从起点到终点的所有路径中，具有最长路径长度的那一路径被定义为关键路径。位于关键路径上的各项活动则被称为关键活动。

唯有对关键路径中的关键活动进行时间上的压缩，才能有效缩短整个工程项目的总工期。

通过计算所有活动中最早可能开始的时间与最晚可以开始的时间，并进行对比分析：若两者数值相等，则表明该项活动属于关键活动，其所处的路径即为关键路径；若不相等，则说明该活动并非关键活动。

以下程序已在DEV C++环境下成功编译并运行通过。

 #include <stdio.h>

    
 #include <stdlib.h>
    
 #de