要求解关键路径，我们要接触一个新的概念AOE网。在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫作边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

AOE网的性质如下：

（1）只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；

（2）只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

在AOE网中存在唯一的、入度为零的顶点，叫作源点；存在唯一的、出度为零的顶点，叫作汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫作关键路径。关键路径上的活动叫作关键活动。这些活动中的任意一项活动未能按期完成，则整个工程的完成时间就要推迟。相反，如果能够加快关键活动的进度，则整个工程可以提前完成。

例如，在图7－30所示的AOE网中，共有9个事件，分别对应顶点v1到v9。其中v1为源点，表示整个工程可以开始。事件v5表示a4、a5已经完成，a7、a8可以开始。v9为汇点，表示整个工程结束。v1到v9的最长路径（关键路径）有两条：（v1，v2，v5，v8，v9）或（v1，v2，v5，v7，v9），长度均为18。关键活动为（a1，a4，a7，a10）或（a1，a2，a8，a11）。关键活动a1计划6天完成，如果a1提前2天完成，则整个工程也可以提前2天完成。

图7－30 AOE网

关键路径我们要如何求得呢？我们需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径；如果不相等，就不是关键路径。

为此，我们需要定义以下几个参数：

（1）事件vi的最早发生时间ve（i）：从源点到顶点vi的最长路径的长度，叫作事件vi的最早发生时间。

（2）事件vi的最晚发生时间vl（i）：在保证汇点按其最早发生时间发生这一前提下，事件vi的最晚发生时间。

（3）活动ai的最早开始时间e（i）：即弧ai最早开始时间。

（4）活动ai的最晚开始时间l（i）：即弧ai最晚开始时间，即在保证事件vk的最晚发生时间为vl（k）的前提下，活动ai的最晚开始时间为l（i）。