用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……
<i,j>S, 1<=i<=n-1
其中，S是所有以i为弧尾的弧的集合。
两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。 3.2 算法步骤
(1)输入e条弧<j,k>，建立AOE网的存储结构。
(2)从源点v1出发，令ve(1)=0,按拓扑有序求其余各顶点的最早发生时间ve(i)（2<=i<=n）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。
(3)从汇点vn出发，令vl(n)=ve(n),求 按逆拓扑有序求其余各顶点的最迟发生时间vl(i)（1<=i<=n-1）。
(4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。 4．程序流程图