7.6.2　关键路径算法

求关键路径的基本步骤如下：

（1）对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件最早发生时间ve（i）；

（2）按逆拓扑序列求每个事件的最晚发生时间vl（i）；

（3）求出每个活动ai的最早开始时间e（i）和最晚发生时间l（i）；

（4）找出e（i）＝l（i）的活动ai，即为关键活动。

下面以图7－30为例。

（1）求v（i）最早开始时间ve（i）：可从源点开始，按拓扑顺序向汇点递推，公式是：

其中，T为所有以i为头的弧＜k，i＞的集合，dut（＜k，i＞）表示与弧＜k，i＞对应的活动的持续时间。图中各个事件的最早开始时间求解过程如下：

ve（1）＝0

ve（2）＝max｛ve（1）＋dut（＜1，2＞）｝＝6

ve（3）＝max｛ve（1）＋dut（＜1，3＞）｝＝4

ve（4）＝max｛ve（1）＋dut（＜1，4＞）｝＝5

ve（5）＝max｛ve（2）＋dut（＜2，5＞），ve（3）＋dut（＜3，5＞）｝＝7

ve（6）＝max｛ve（4）＋dut（＜4，6＞）｝＝7

ve（7）＝max｛ve（5）＋dut（＜5，7＞）｝＝16

ve（8）＝max｛ve（5）＋dut（＜5，8＞）｝＝14

ve（9）＝max｛ve（7）＋dut（＜7，9＞），ve（8）＋dut（＜8，9＞）｝＝18

（2）求v（i）最晚开始时间vl（i）：在求出ve（i）的基础上，可从汇点开始，按逆拓扑顺序向源点递推，求出vl（i），公式如下：

vl（n）＝ve（n）

vl（i）＝min｛vl（k）－dut（＜i，k＞）｝＜i，k＞∈S，0≤i≤n

其中，S为所有以i为尾的弧＜i，k＞的集合，dut（＜i，k＞）表示与弧＜i，k＞对应的活动的持续时间。图中各事件的最晚开始时间求解过程如下：

vl（9）＝ve（9）＝18

vl（8）＝min｛vl（9）－dut（＜8，9＞）｝＝14

vl（7）＝min｛vl（9）－dut（＜7，9＞）｝＝16

vl（6）＝min｛vl（8）－dut（＜6，8＞）｝＝10

vl（5）＝min｛vl（7）－dut（＜5，7＞），vl（8）－dut（＜5，8＞）｝＝7

vl（4）＝min｛vl（6）－dut（＜4，6＞）｝＝8

vl（3）＝min｛vl（5）－dut（＜3，5＞）｝＝6

vl（2）＝min｛vl（5）－dut（＜2，5＞）｝＝6

vl（1）＝min｛vl（2）－dut（＜1，2＞），vl（3）－dut（＜1，3＞），vl（4）－dut（＜1，4＞）｝＝0

（3）活动ai的最早开始时间e（i）：即如果活动ai对应的弧为＜j，k＞，则e（i）等于从源点到顶点j的最长路径的长度，即e（i）＝ve（j）。

e（a1）＝ve（1）＝0

e（a2）＝ve（1）＝0

e（a3）＝ve（1）＝0

e（a4）＝ve（2）＝6

e（a5）＝ve（3）＝4

e（a6）＝ve（4）＝5

e（a7）＝ve（5）＝7

e（a8）＝ve（5）＝7

e（a9）＝ve（6）＝7

e（a10）＝ve（7）＝16

e（a11）＝ve（8）＝14

（4）活动ai的最晚开始时间l（i）：如果活动ai对应的弧为＜j，k＞，其持续时间为dut（＜j，k＞），则有l（i）＝vl（k）－dut（＜j，k＞），即在保证事件vk的最晚发生时间为vl（k）的前提下，活动ai的最晚开始时间为l（i）。

l（a11）＝vl（9）－dut（＜8，9＞）＝14

l（a10）＝vl（9）－dut（＜7，9＞）＝16

l（a9）＝vl（8）－dut（＜6，8＞）＝10

l（a8）＝vl（8）－dut（＜5，8＞）＝7

l（a7）＝vl（7）－dut（＜5，7＞）＝7

l（a6）＝vl（6）－dut（＜4，6＞）＝8

l（a5）＝vl（5）－dut（＜3，5＞）＝6

l（a4）＝vl（5）－dut（＜2，5＞）＝6

l（a3）＝vl（4）－dut（＜1，4＞）＝3

l（a2）＝vl（3）－dut（＜1，3＞）＝2

l（a1）＝vl（2）－dut（＜1，2＞）＝0

由求解过程可以得到如图7－31所示的事件图和活动图，由图中信息可以得到，关键路径即ve（i）＝vl（i）组成的路径，关键活动即e（i）＝l（i）的活动。

图7－31 事件图和活动图

由此可以看出，图具有两条关键路径，一条是由v1，v2，v5，v7，v9组成的关键路径，另一条是由v1，v2，v5，v8，v9组成的关键路径，如图7－32所示。

图7－32 关键路径

关键路径算法如下：可以看到，求事件的最早发生时间的过程，就是从头至尾找拓扑排序的过程，因此在求关键路径之前，需要先调用一次拓扑排序算法的代码，下面首先修改上一节的拓扑排序算法，以便同时求出每个事件的最早发生时间ve（i）。

算法7.8 修改后的拓扑排序算法

有了每个事件的最早发生时间，就可以求出每个事件的最迟发生时间，进一步可求出每个活动的最早开始时间和最晚开始时间，最后就可以求出关键路径了。求关键路径的算法实现如下。

算法7.9 关键路径算法

算法的时间复杂度为O（n＋e）。