数据结构重读 – AOV网和关键路径

与AOV网对应的,还有一个AOE网,当然它也是有DAG(向无环图)。

AOE(Activity On Edge)网:顾名思义,用边表示活动的网。

与AOV不同,活动都表示在了边上,如下图所示:

如上所示,共有11项活动(11条边),9个事件(9个顶点)。

整个工程只有一个开始点和一个完成点

只有一个入度为零的点(源点)和只有一个出度为零的点(汇点)。

(1) 关键路径:是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。

(2) 最早发生时间:v1到vi的最长路径叫做vi的最早发生时间,用ei表示。例如上图中,v5的最早发生时间是max(6+1, 4+1) = 7。

(3) 最迟开始时间:在不推迟整个工程完成的前提下,活动i最迟必须开始进行的时间,用l(i)表示。l(i) – e(i)是活动的时间余量。

(4) 关键活动:l(i)=e(i)的活动称为关键活动。

关键路径上的活动都是关键活动。

提前完成非关键活动并不能加快工程进度(类似木桶效应)。

AOE网的主要活动就是识别出哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。

当然,如果AOE网发生了改变,那么原先的关键路径也会发生变化。

因此,只有在不改变挂件路径的情况下,提供关键活动的速度,才能对整体工程进度起到帮助作用。

求关键路径的算法

求关键路径,就是要求e(i) = l(i)的事件(点)。我们首先必须分别求出所有点的e(i)和l(i)。

由于ve和vl的递推公式必须在拓扑排序下有效,因此,先要求拓扑排序

0、求拓扑排序(同时顺道求ve)

要增设一个栈T记录拓扑有序序列,计算求得各个顶点的ve之后,从栈顶依次弹出栈,就可以倒序遍历,求vl了。

还要使用拓扑排序的那个入度为0的栈,可以每次Pop时候顺道记录下,最后cnt如果<g->nvexs,则表示有环。

1、求最早发生时间ve[]

ve(0)=0开始递推

ve(j) = max{ve{i}+dut(i, j)}

2、求最晚发生时间vl[]

从vl(n-1)=ve(n-1)开始倒推。

vl(j) = min{vl(i) – dut(j, i)}。

3、遍历,求出ve(i) = vl(i)的所有点i。

算法总时间复杂度是O(n+e)。

具体的代码如下:

求拓扑排序和ve、以及栈T

求vl

求关键路径

其他代码,如创建等,注意我们要存储活动的耗费,给Arc加了一个权值w。

测试驱动:

测试AOE图:

测试数据:

测试输出:

 

 

Leave a Reply

Your email address will not be published.