详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)

2020-01-06 13:45:16王旭

如图是一个假想的有11项活动的AOE-网:

详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)

其中有9个事件v1,v2,v3,…,v9,每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。如v1表示整个工程开始,v9表示整个工程结束,v5表示a4和a5已经完成,a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如,活动a1需要6天,a2需要4天等。

和AOV-网不同,对AOE-网有待研究的问题是:
(1)完成整项工程至少需要多少时间?
(2)哪些活动是影响工程进度的关键?

3.3 关键路径

由于在AOE-网中有些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。

AOE网有关的概念:
1)路径长度:路径上各个活动的持续时间之和

2)完成工程的最短时间:由于AOE网中有活动是并行进行的,所以完成工程的最短时间就是从开始点到完成点的最长路劲长度。
3)活动最早开始时间(earlist time)(e(i)):从开始点到顶点vi的最长路径称为事件vi的最早发生时间。这个时间决定了以vi为尾的弧表示的活动的最早开始时间.
4)活动最晚开始时间(latest time)(l(i)):在不推迟整个工程完成的前提下,活动最迟开始的时间
5)完成活动的时间余量:该活动的最迟开始时间减去最早开始时间
6)关键路径(critical path):路径长度最长的路径称为关键路径
7)关键活动(critical activity):关键路径上的活动称为关键活动,关键活动的特点是:e(i)=l(i)分析关键路径的目的就是辨别在整个工程中哪些是关键活动,以便争取提高关键活动的工作效率,缩短整个工程的工期。
3.4 解决方案:
由上分析可知,辨别关键活动就是要找e(i)=l(i)的活动。为了求得AOE-网中活动的e(i)和l(i), 首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧<j,k>表示,其持续时间记为dut(<j,k>),则有如下关系: