第7章 图 7.6 AOE网与关键路径《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第7章 图 7.1 图的基本概念 7.2 图的存贮结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.5.2 AOE网与关键路径 一、AOE网概念 1.定义(Activity On Edge) 若在带权的有向图中,以顶点表示事件,有向边表示活动，边上的权值表示完成该活动的开销（如该活动所需的时间），则称此带权的有向图为用边表示活动的网络，简称AOE网。2.说明 (1) AOV网与AOE网有密切关系又有不同。如果用他们表示工程，AOV网表示各个子工程之间的优先关系，是定性关系；在AOE网中还要体现完成各个子工程的确切时间，是定量关系。对于AOE网，我们关心的问题是： （A）完成整个工程至少需要多少时间？ （B）哪些活动是关键活动：哪些活动的进度是影响整个工程进度的关键？ （2）在AOE网中，只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入每顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。 （3）在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入度为零的顶点，乘作开始顶点，它表示了整个工程的开始；网中仅存在一个出度为零的顶点，称为结束顶点，它表示整个工程的结束。 3. AOE网实例 v1 v2 v4 v5 v8 v10 v7 v6 v3 v9 a1=3 a2=2 a3=6 a4=3 a5=8 a6=4 a7=2 a8=7 a9=4 a10=6 a11=9 a12=6 a13=5 a14=4 a15=8 图7.5.1 一个工程的AOE网 二、关键路径有关术语 1.路径长度 AOE网中一条路径的长度是该路径上个活动所需时间的总和。 2.关键路径 AOE网中,从开始顶点到结束顶点之间路径长度中的最大路径为关键路径。由于AOE网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程AOE网的关键路径长度。 3.事件的最早发生时间ve(i) 事件vi的最早发生时间ve(i)是从开始顶点v到vi的最长路径长度。 4.活动的最早开始时间e (j) 活动aj的最早开始时间e (j)是该活动的起点所表示的事件最早发生时间，如果由边(vi,vk)表示活动aj，则有e(j)=ve(i)。 5.事件的最迟发生时间vl(k) 事件vk的最迟发生时间vl(k)是在不推迟整个工程完成(即保证结束顶点vn在ve(n)时刻发生)的前提下，该事件最迟必须发生的时间。vl(k)为ve(n)减去顶点vk到结束顶点vn的最长路径的长度。 6.活动的最迟开始时间l(j) 活动aj的最迟开始时间l(j)是该活动的终点所表示的事件最迟发生时间与该活动的所需时间之差。如果由边(vi,vk)表示活动aj，则有：l(j)=vl(k)-aj所需时间。 7.时间余量 活动aj的 l(j)-e(j)是该活动完成的时间余量。它是在不增加完成整个工程所需时间的情况下，活动aj可以拖延的时间。 8.关键活动 当一活动的时间余量=0，说明该活动必须如期完成，否则就会拖延完成整个工程的进度。若活动aj的时间余量=0，则称该活动为关键活动。当时间余量>0，活动aj不是关键活动，只要拖延的时间不超过时间余量，就不会影响整个工程的进度；但如果拖延的时间超过时间余量，则关键活动就可能发生变化。 三、求关键路径步骤： 1、从开始顶点出发，计算各事件的最早发生时间ve(i) 递推公式 ve(1)=0 ve(k)=max{ve(j)+<vj, vk>上的权} <vj, vk>为所有到达vk的有向边 递推公式的实现方法 按拓扑有序求其余各顶点的最早发生时间。 在拓扑排序过程中，每输出一个顶点j之后，利用ve[j]对vj的每一个后续顶点vk修正ve[k] 。 求解过程的示例 v1 v2 v4 v5 v8 v10 v7 v6 v3 v9 a1=3 a2=2 a3=6 a4=3 a5=8 a6=4 a7=2 a8=7 a9=4 a10=6 a11=9 a12=6 a13=5 a14=4 a15=8 2、计算事件的最迟发生时间vl（k） 递推公式 vl(n)=ve(n) vl(k)=min {vl(j)-<vk,vj>上的权 } <vk,vj>为所有从vk出发的有向边 递推公式的实现方法 上式是一个从结束顶点开始的向前递推的公式，可以按拓扑序列的逆序依次取每个顶点vk，用上述递推公式计算vl[k]。 求解vl[k]示例 前已求得拓扑序列为(1,2,3,4,5,8,6,7,9,10)， 其逆序为(1