7.5.2 关键路径在线视频

同学们大家好

这节课我们讨论有向无环图的关键路径算法

关键路径算法是基于AOE网实现的

AOE网是用边表示活动网

是一个带权的有向无环图

其中，顶点表示事件，弧表示活动

权表示活动持续的时间

通常AOE网用来估算工程的完成时间

在AOE网中，顶点表示的是事件

事件是一个瞬时的概念，表示发生了某种情况

事件本身不占时间

例如图中顶点v5

它表示的是a4, a5两个活动都完成了

有两个比较特殊的事件，一个称为源点

图中是v1，表示工程活动开始

另外一个称为汇点，图中是v9，它表示整个工程完工

基于AOE网，我们要解决的问题有两个

一是，完成这项工程需要多少时间？

二是，那些活动是影响工程进度的关键？

我们先来定义关键路径的

路径的长度为路径上各活动的持续的时间之和

从源点到汇点最长的路径称为关键路径

从源点到汇点，可能有很多条路径

甚至最长的路径也不止一条

图中有一条最长的路径是v1,v2,v5,v7,v9

路径的长度是18，还有一条v1,v2,v5,v8,v9，长度也是18

一条路径上，前后的活动之间有约束

也就是前一个活动未完成，后一个活动不能开始

例如活动a1和a4，a1没有完工，a4不能开始

由此，最长路径上的活动只能按顺序完成

它代表的是一个工程完工的最短时间

最长路径被称为关键路径

所有关键路径上的活动称为关键活动

图中这样活动有6个，a1,a4,a7,a8,a10,a11

关键路径算法的目标就是求出所有关键活动

因为图中求两个顶点之间所有路径的算法时间复杂度很高

我们不采用求出所有路径

再求关键活动的办法，采用的是另外的方法

介绍关键路径算法前，先定义几个概念

事件的最早发生时间和活动的最早开始时间

假设开始点是v1，从v1到vj的最长路径长度

叫做事件vj的最早发生时间

vj发生后

以vj为弧尾的活动可以开始进行

若ai是以vj为弧尾的活动

则ai的最早开始时间等于事件vj的最早发生时间，用e(i)表示

看图，从v1到v5有两条路径

v1，v2，v5这一条长度为7

v1，v3，v5这一条长度为5

那么根据定义，v5的最早发生时间是第7天

事件v5的含义是活动a4,a5都完成了

从活动之间的约束和路径长度看

只有到第7天才能保证a4,a5都完成了

从v1到v6只有一条路径

长度为7，v6的最早发生时间也是第7天

以v5为尾的活动有：a7和a8

那么a7和a8的最早开始时间e(7)和e(8)都等于7

以v6为尾的活动有：a9，a9最早开始时间e(9)=7

下面定义活动的最迟开始时间l(i)，l(i)的含义是

在不推迟整个工程完成的前提下

活动ai最迟必须开始进行的时间

刚才看到整个工程的最短工期是18天

那么在不推迟18天工程完工的前提下

考虑活动的最迟开始时间

以a8和a9为例，a8对后续活动a11有约束

a11需要4天，a8自身还需要7天

所以在不耽误工程的前提下

a8第7天必须开始，于是l(8)等于7

a9的后续活动也是a11，需要4天

自身需要4天，所以l(9)等于7

刚才讨论过，活动a8和a9的最早开始时间e(8)和e(9)都等于7

那么对活动a8来说，它的最早开始时间是第7天

在不耽误工期的前提下，最迟开始时间也是第7天

而a9呢，它的最早开始时间是第7天

不耽误工期的前提下，最迟可以第10天再开始

那么l(i)-e(i)意味着完成活动ai的时间余量

若l(i)=e(i)，则活动ai为关键活动

从上面的讨论可以看到a8是关键活动

这样的活动延期，必将导致整个工程的延期

而a9是有时间余量的

耽误两天也不会影响整个工程的建设

关键路径算法的目的就是计算所有活动的e(i)和l(i)

随后，根据二者是否相等判断是否是关键活动

为了计算所有活动的e(i)和l(i)

我们先求出每个事件的最早发生时间和最迟发生时间

设ve(j)是事件j的最早发生时间

vl(j)是事件j的最迟发生时间

事件的最迟发生时间的含义是

在不推迟整个工期的前提下，该事件发生的最迟时间

活动ai由弧j, k表示，

其持续时间记为dut (＜j,k＞)

顺便声明一下

后续讨论中都假设顶点v1到vn

存储位置是0到n-1

先求出所有事件的最早发生时间

源点事件的最早发生时间是0

其它事件的最早发生时间ve(j)

等于MAX{ve(i)+dut(＜i，j＞)}

＜i,j＞∈ T

T是所有以第j个顶点为头的弧的集合

公式的含义是：i是j的前驱

用前驱的ve(i)加i到j这个活动的权值

如果j有多个前驱

取ve(i)加dut(＜i,j＞)，j最大的作为ve(j)的值

通过例子看一下

图中v2只有一个唯一的前驱v1

所以v2的最早发生时间

ve(1)=0+6=6

v3也只有一个唯一的前驱v1

ve(2)=0+4=4

v5有两个前驱v2和v3

分别求ve(i)+dut(＜i,j＞)

为7和5

那么ve(4)取大等于7

就是v5的最早发生时间是第7天

前面说过事件v5的含义是活动a4,a5都完成了

从前驱v2看，v2最早发生时间是第6天

v2发生后，a4可以开始，a4需要1天

也就说第7天a4才能完成

从v3看，第5天可以完成a5

而v5的含义是活动a4,a5都完成了，所以只能取最大值

下面求每个事件的最迟发生时间

vl(n-1)=ve(n-1)意思是说

汇点的最迟发生时间等于其最早开始时间

就这个例子来说是18天

其它顶点的最迟发生时间由公式

vl(i)=Min{vl(j)-dut(＜i,j＞)}

其中

＜i,j＞∈ S

S是所有以第i个顶点为尾的弧的集合

公式的含义是：找顶点i的后继顶点j

用顶点j的最迟发生时间减i到j活动的持续时间

如果有多个后继

取vl(j)减dut(＜i,j＞)最小的

作为vl(i)的最迟发生时间

从公式可以看出

求vl(i)必须知道它后继的最迟发生时间

我们开始只知道汇点的最迟发生时间

所以求最迟发生时间是从汇点向前

借助图例来看一下

汇点v9的最迟发生时间是18

对顶点v7来说，只有一个唯一的后继是汇点

按公式v7的最迟发生时间vl(6)=16

同理，v8的最迟发生时间vl(7)=14

v5的两个后继

v7,v8已经求得最迟发生时间

按公式计算

vl(6)-dut(＜4,6＞)=7

vl(6)-dut(＜4,7＞)=4

取小，vl(4)等于4

观察图，v5发生后

a8和a11才能依次执行

两个活动共需要14天，不耽误工期的话

v5最迟第4天必须发生

如果通过上述步骤已经求得了

事件顶点的最早发生时间和最迟发生时间

随后就可以计算每个活动的最早开始时间和最迟开始时间

设ai由弧＜j, k＞表示

其持续时间记为dut(＜j,k＞)

如图所示

活动ai的弧尾是j，弧头是k

那么活动ai的最早开始时间

e(i)等于顶点j的最早发生时间ve(j)

活动ai的最迟开始时间l(i)等于顶点k的

最迟发生时间vl(k)减去ai持续的时间

求出所有活动的e(i)和l(i)之后

如果活动i的e(i)和l(i)相等，则活动i是关键活动

前面介绍了求事件最早和最迟发生时间的原理

那么利用算法怎么求所有顶点的最早和最迟发生时间呢？

这里把算法实现的主要思路介绍一下

首先求所有顶点的最早发生时间

先做初始化

把所有顶点的最早发生时间都初始化为0

如图1所示

求最早发生时间是从源点出发

按顶点的拓扑排序序列处理每个顶点

注意这一步非常关键

按照拓扑序列处理

可以保证处理到顶点i的时候

拓扑序列中的顶点i所有前驱都已经被处理过了

处理到顶点i时

i的最早发生时间已经求得

观察图1

设拓扑序列为v1,v4,v6,v3,v2,v5,v8,v7,v9

第一个顶点肯定是源点，最后一个顶点肯定是汇点

处理顶点i时，考察它的所有后继

当正在考察的后继为k时

如果ve(i)加dut(＜i，k＞)，大于ve(k)

就是顶点i的最早发生时间加i到j这条弧的持续时间

如果大于后继目前的最早发生时间

则把ve(i)加dut(＜i，k＞)赋值给做更新

同学们注意，如果k有多个前驱

那么在按拓扑序列处理到k之前

vl(k)可能多次更新

保留下最大值作为vl(k)的最终结果

结合图1，简单说一下

源点v1的最早发生时间ve(0)是0

这是已经知道的

处理v1，有3个后继v2,v3,v4

处理后ve(1)=6，ve(2)=4，ve(3)=5

这三个顶点没有其它前驱

这就是它们的最早发生时间

结果如图2所示

按拓扑序列，随后处理v4

有一个后继

ve(5)=7，继续处理v6

后继v8的最早发生时间ve(7)目前是11

不一定是最终值

因为v8有两个前驱

要等v5处理完后，才是最终结果

后续过程类似，就不重复了

求顶点最早发生时间的函数是在拓扑排序函数的基础上修改获得

同学们课后认真读下程序

另外，在求顶点最早发生时间的函数中

按照拓扑序列把顶点入了一个栈

为后面求顶点的最迟发生时间做准备

求最迟发生时间时，是按照拓扑逆序

从汇点开始向前求，按照拓扑序入栈

后进先出，出栈就是拓扑逆序

下面看求顶点的最迟发生时间

求每个顶点的最迟发生时间

首先初始化

所有顶点的vl都初始化为ve(n-1)

也就是汇点的最早发生时间

示例中是18，结果如图1所示

随后按拓扑逆序求每个顶点i的最迟发生时间

方法是考察顶点i的每个后继

当考察的后继是k时

如果vl(k)减dut(＜i，k＞)小于vl(i)

就是后继k的最迟发生时间减i到k这条弧的持续时间

小于当前顶点i的最迟发生时间

则把vl(i)更新为vl(k)减dut(＜i，k＞)

考察完顶点i的所有后继之后

vl(i)中就是顶点i最终的值

观察图2

拓扑逆序第一个顶点是v9

v9没有后继，不必处理

v9的最迟发生时间就是18

v7,v8都只有一个后继是汇点

按上述方法

vl(6)=16,vl(7)=14

随后处理v5，v5有两个后继v7,v8

计算的结果都是7

那么vl(4)=7

后续过程就不重复了

按照拓扑逆序求顶点的最迟发生时间

当求到顶点i的时候

i的所有后继的最迟发生时间都已经求得

根据前面的讨论

求得顶点的最早和最迟发生时间之后

可以获得每个活动的最早开始时间和最迟开始时间

然后找出最早开始时间和最迟开始时间相等的活动

这些活动就是AOE网的关键活动

好，同学们这节课就讲到这儿

下次课再见