数据结构课件：AOE网与关键路径.pptx

AOE网与关键路径

本讲要点什么是AOE网？什么是关键路径？查找关键路径算法

1.AOE网的概念AOE网：在一个有向图中，用顶点表示事件，弧表示活动，弧上的权值表示该活动的持续时间，称这种有向图为边表示活动的网，简称AOE网（ActivityonEdgeNetwork）。v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4事件事件含义v1开工v2活动a1完成，活动a4可以开始v3活动a2完成，活动a5可以开始…………v9活动a10和a11完成，整个工程完成

1.AOE网的概念对于AOE网要研究的两个主要问题：1）完成整项工程至少需要多少时间？2）哪些活动是影响工程进度的关键？v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。具有最大长度的路径称为关键路径。关键路径上的活动称为关键活动。

2.查找关键路径算法要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动。首先计算以下与关键活动有关的量：事件的最早发生时间ve[k]事件的最迟发生时间vl[k]活动的最早开始时间e[i]活动的最晚开始时间l[i]最后计算各个活动的时间余量l[k]-e[k]，时间余量为0者即为关键活动。

2.查找关键路径算法v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8ve[i]064577161418ve[i]=max{ve[j]+wvj,vi}（1）事件vi可能的最早发生时间ve(i)

2.查找关键路径算法v2v7v6v5v4v1v3v9v8ve[i]vl[i]0645771614181814161078660vl[i]=min{vl[j]-wvi,vj}（2）事件vi允许的最迟发生时间vl(i)v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4

2.查找关键路径算法v2v7v6v5v4v1v3v9v8ve[i]064577161418a2a7a6a5a4a1a3a9a8e[k]000645777a10a111614e[k]=ve[i]（3）活动ak=〈vi,vj〉可能的最早开始时间e(k)v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4

2.查找关键路径算法l[k]10778663201614a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vl[j]1814161078660l[k]=vl[j]-wvi,vj（4）活动ak=〈vi,vj〉允许的最迟开始时间l(k)v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4

2.查找关键路径算法a2a7a6a5a4a1a3a9a8e[i]l[i]000645771077866320a10a1116141614v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4关键活动：l[i]=e[i]的活动7

2.查找关键路径算法若AOE网中有几条关键路径，那么提高一条关键路径上的关键活动的速度，能不能缩短整个工程的工期？v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4

本讲要点什么是AOE网？什么是关键路径？查找关键路径算法