在学习拓扑排序一节中论述拓扑排序只适用于AOV网，本节介绍的关键路径是以接近AOV网的AOE网为对象的。
AOE网络
AOE网基于AOV网，每边各有权重，是有向无环网。 在这里，权重表示活动的持续时间。
如图1所示，在AOE网络中，例如a1=6表示完成a1活动需要6天； AOE网的各顶点表示其前一个活动已经完成，可以开始后一个活动。 例如，V5表示a4和a5活动已完成，a7和a8可以开始。
使用AOE网络时，如果将AOE网络视为整个项目，则完成整个项目至少需要多长时间？
解决这个问题的关键是找出从AOE网络点到终点长度最长的路径，确保在所有活动结束之前完成。
起点是点为0的点，称为“源点”； 终点是出度为0的点，称为“汇点”。 这条最长的路径被称为“关键路径”。
关键路径
为了求出给定的AOE网络的关键路径，需要知道以下4个统计数据。
在AOE网络的顶点，有最早的发生时刻(用ve ) j表示)和最晚的发生时刻(用VL ) j表示)两个时间。
边缘也具有两个时间：最早开始时间(由e ) I表示)和最晚开始时间(由l ) I表示)。
对于任何一个AOE网顶点，ve(j )从源到该点的最长路径表示该顶点的最早发生时间，通常用ve(j )表示。
例如，在图1中从V1到V5有两个路径，在V1作为源点开始后，a1和a2同时开始活动，但是由于a1和a2的活动的时间长度不同，最终V1-V3-V5的该路径先完成。 但是，V5以后的活动并不是可以开始的，V1-V2-V5这一路径也需要在完成之后开始。 因此，对于V5来说，ve(5)=7。
VL(j )表示事件Vk允许的最晚发生时间，而不延迟整个工期。
例如，图1假设整个工期的完成时间为18天，但V7最迟在第16天开始。 a10活动至少需要两天才能完成，因此如果V7事件延迟，整个工期就会延迟。 因此，对V7来说，其VL(7)=16。
e(I ) :表示活动ai的最早开始时间，如果活动ai由弧表示，则活动ai的最早开始时间等于时间Vk的最早发生时间。 即e[i]=ve[k]。
e ) I )我很明白。 用图1的a4来说，如果a4要开始活动，首先前提是V2事件开始。 所以e[4]=ve[2]。
L(I ) :表示活动ai的最迟开始时间。 如果活动ai用弧形表示，则ai的最大延迟开始时间的设置不会延长Vj的最大延迟发生时间。 因此，l[i]=Vl[j]-len。
知道以上四种统计数据后，可以直接求出AOE网关键路径上的所有关键活动。 此方法对所有边缘来说，如果其最早的开始时间等于最晚的开始时间，则将边缘表示的活动称为关键活动。 由关键活动组成的路径是关键路径。
寻求关键路径的具体过程
针对图1的AOE图求出关键路径，首先完成ve(j )、VL )、ve(j )、l (I ) 4种统计信息的准备。
ve(j )将从源到各顶点的最长路径长度作为(长度最大的)求出
VL(j )求出各顶点最迟发生时间(从后向前按，往往选择最小的) :
e(I )求出各边的ai活动的最早开始时间：
L(I )求出各边的ai活动的最慢的开始时间(往往选择最小的) :
比较L(I )和L(I )，其中a1、a4、a7、a8、a10、a11的值分别相同，因此图1的AOE网有两个关键路径。
图2关键路径
关键路径的代码实现
#包含
#包含
#define MAX_VERTEX_NUM 20//最大顶点数
#define VertexType int//顶点数据的类型
typedef enum{false，true} bool；
//创建全局变量，保存边缘的最早开始时间
VertexType ve[MAX_VERTEX_NUM]；
//创建全局变量，保存边缘的最晚开始时间
VertexType vl[MAX_VERTEX_NUM]；
类型结构arcnode {
int adjvex； //邻接点为
以图1的AOE网为例，运行结果如下。
九一一
1
2
3
4
5
6
7
8
9
1，2，6
1，3，4
1，4，5
2，5，1
三五一
4，6，2
5，7，9
5，8，7
6，8，4
7，9，2
8，9，4
0 3 5 0 3
0 2 4 0 2
060、0、0*
1 4 1 6 6 *
2 4 1 4 6
3 5 2 5 8
4 7 7 7 7 *
49(7)7*
5 7 4 7 10
62161616*
7 8 4 14 14 *
根据执行结果，键活动有6个，后面标记有* )，构成的键路径如图2所示。