数据结构 关键路径与最短路径

7.5.2 关键路径

对整个工程和系统，人们关心的是两个方面的问题：\r\n    1）工程能否顺利进行\r\n       对AOV网进行拓扑排序\r\n    2）估算整个工程完成所必须的最短时间\r\n       对AOE网求关键路径

AOE-网

AOE－网(Activity On Edge Network)：即边表示活动的网。AOE网是一个带权的有向无环图。其中：\r\n顶点表示事件（Event）\r\n弧表示活动（Activity）\r\n权值表示活动持续的时间\r\n\r\n  通常可用AOE网来估算工程的完成时间。

上图AOE-网中：\r\n  共有11项活动：a1,a2,a3,…a11；\r\n  共有9个事件：v1,v2,v3,…v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。

v9\r\n表\r\n示\r\n整\r\n个\r\n工\r\n程\r\n的\r\n结\r\n束

v5表示a4和a5已经完\r\n成， a7和a8可以开始

与每个活动相联系的数是执行该活动所需的时间

v1\r\n表\r\n示\r\n整\r\n个\r\n工\r\n程\r\n的\r\n开\r\n始

由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（称作汇点）

汇点

源点

依据AOE-网可以研究什么问题？

（1）完成整项工程至少需要多少时间？\r\n\r\n（2）哪些活动是影响工程进度的关键？

完成工程的最短时间是从源点到汇点的最长路径的长度。路径长度最长的路径叫做关键路径。\r\n    从v1到v9的最长路径是（v1,v2,v5,v8,v9），路径长度是18。

假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。\r\n    用e(i)表示活动ai的最早开始时间。

V9的最早发生时间是18

事件vi的最早发生时间

l(i)－e(i)两者之差意味着完成活动ai的时间余量。我们把l(i)＝e(i)的活动叫做关键活动。\r\n    显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。

a6的最早开始时间是5，最迟开始时间是8。如a6推迟3天开始或延迟3天完成，都不会影响整个工程的完成。

活动的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。

由此可知：辨别关键活动就是找e(i)＝l(i)的活动。为求得AOE网中活动的e(i)和l(i)，首先应求得事件的最早发生时间 ve(j)和 最迟发生时间vl(j)。\r\n    若活动ai由弧表示，持续时间记为dut()，则有如下关系：\r\n     \r\n    活动i的最早开始时间等于事件j的最早发生时间\r\n          e(i)＝ ve(i)\r\n    活动i的最迟开始时间等于事件k的最迟时间减去活动i的持续时间\r\n          l(i)＝ vl(j) - dut()\r\n    求ve(j)和 vl(j)需分两步进行：

ve[j]和vl[j]可以采用下面的递推公式计算：\r\n（1）向汇点递推\r\n    ve(源点) = 0 ；\r\n    ve(j) = Max{ ve(i)   dut()}

公式意义：从指向顶点Vj的弧的活动中取最晚完成的一个活动的完成时间作为Vj的最早发生时间ve[j]

（2） 向源点递推\r\n     由上一步的递推，最后总可求出汇点的最早发生时间ve[n]。因汇点就是结束点，最迟发生时间与最早发生时间相同，即vl[n]=ve[n]。从汇点最迟发生现时间vl[n]开始，利用下面公式：\r\n\r\n\r\n    vl(汇点) = ve(汇点);\r\n    vl(i) = Min{ vl(j) – dut() }

公式意义：由从Vi顶点指出的弧所代表的活动中取需最早开始的一个开始时间作为Vi的最迟发生时间。

由此得到下述求关键路径的算法：\r\n1）输入e条弧，建立AOE网的存储结构。\r\n2）从源点v0出发，令ve[0]＝0按拓扑有序求其余各顶点的最早发生时ve[i]（1≤i≤ n-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。\r\n3）从汇点vn出发，令vl[n-1]= ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i] (n-2 ≥i≥ 0)；\r\n4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。

如上所述，计算顶点的ve值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：\r\n    1）在拓扑排序之前设初值，令ve(i)=0（0<=i<n-1）;\r\n    2）在算法中增加一个计算vi的直接后继vj的最早发生时间的操作：若 ve(i) dut() > ve(j), 则 ve(j) = ve(i) dut()；\r\n    3）为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，则需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的 ve 值之后，从栈顶至栈底便为逆拓扑有序序列。

总之，关键路径的求解操作包括：\r\n1）计算 ve[j] 和 vl[j] \r\n ① 向汇点递推\r\n ve(源点) = 0 ；\r\n ve(j) = Max { ve(i)  dut()}\r\n ② 向源点递推\r\n vl(汇点) = ve(汇点);\r\n vl(i) = Min { vl(j) – dut()}