2010软件水平考试软件设计师重点难点辅导(3)2

 　　为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量：

　　Ve(j)、Vl(j) ：顶点j事件最早、最迟发生时间。

　　e(i)、l(i)：活动i最早、最迟开始时间。

　　从源点V1到某顶点Vj的最长路径长度称为事件Vj的最早发生时间，记为Ve(j)。Ve(j)也是以Vj为起点的出边所表示的活动ai的最早开始时间e(i)。

　　在不推迟整个工程完成的前提下，一个事件Vj允许的最迟发生时间记为Vl(j)。显然，l(i) =Vl( j)-(ai所需时间)，其中j为ai活动的终点。满足条件l(i) =e(i)的活动为关键活动。

　　求顶点Vj的Ve(j)和Vl(j)可按以下两步来做。

　　(1)由源点开始向汇点递推。

　　其中，E1是网络中以Vj为终点的入边集合。

　　(2)由汇点开始向源点递推。

　　其中，E2是网络中以Vj为起点的出边集合。