图：求关键路径

一：概念：

在学习关键路径前，先了解一个AOV网和AOE网的概念：如下图所示

假如汽车生产工厂要制造一辆汽车，制造过程的大概事件和活动时间如上图AOE网：
那么，显然对上图AOE网而言,所谓关键路径：

开始–>发动机完成–>部件集中到位–>组装完成。路径长度为5.5。如果我们试图缩短整个工期，去改进轮子的生产效率，哪怕改动0.1也是无益的。只有缩短关键路径上的关键活动时间才可以减少整个工期的长度。

例如如果制造发动机缩短为2.5天，整车组装缩短为1.5天，那么关键路径为4.5。工期也就整整缩短了一天时间。

好吧！ 那么研究这个关键路径意义何在？
假定上图AOE网中弧的权值单位为小时，而且我们已经知道黑深色的那一条为关键路径。假定现在上午一点，对于外壳完成事件而言，为了不影响工期：外壳完成活动最早也就是一点开始动工，最晚在两点必须要开始动工。最大权值3表示所有活动必须在三小时之后完成，而外壳完成只需要2个小时。所以，这个中间的空闲时间有一个小时，为了不影响整个工期，它必须最迟两点动工。

那么才可以保证3点时与发动机完成活动同时竣工，为后续的活动做好准备。

二：相关术语：

1. AOV网络（Activity On Vertex Network）：有向图，用顶点表示活动，用弧表示活动的先后顺序
2. AOE网络（Activity On Edge）：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间（带权的有向无环图）
3. 活动：业务逻辑中的行为，用边表示
4. 事件：活动的结果或者触发条件
5. 关键路径：具有最大路径长度（权重）的路径，可能不止一条
6. 活动的两个属性：e(i)最早开始时间，l(i)最晚开始时间
7. 事件的两个属性：ve(j)最早开始时间，vl(j)最晚开始时间

三：计算关键路径的过程:

步骤：

1. 先求出每个顶点的ve（最早开始时间）和vl（最晚开始时间）的值
2. 通过这两个值就可以求出每条边的e（最早开始时间）和 l（最晚开始时间）值。
3. 取e(i)=l(i)的边就是关键路径上的边，相连，就能得到关键路径（键路径可能不止一条）

---

①：求ve(j)的值（事件最早开始时间）

1. 从前向后，直接前驱节点的ve值＋当前节点的边的权值（有可能多条，取最大值）
2. 第一个顶点的ve等于0

顶点	V1	V2	V3	V4	V5	V6	V7
ve(j)	0	3	2	6	7	5	10

---

②：求vl(j)的值（事件最迟开始时间）

1. 从后向前（V9开始），直接后继节点的vl值－当前节点的边的权值（有可能多条，取最小值）
2. 终结点的vl等于它的ve

顶点	V1	V2	V3	V4	V5	V6	V7
vl(j)	0	3	3	6	7	6	10

---

③：求e(i)的值（活动最早开始时间）

1. e ( i ):活动ai是由弧< vk,vj >表示，则活动的最早开始时间应该和事件vk的最早发生时间相等，因此，就有e(i)=ve(k)。
   即：边（活动）的最早开始时间等于它发出的顶点(事件)的的最早发生时间

边	a1(3)	a2(6)	a3(2)	a4(4)	a5(2)	a6(1)	a7(3)	a8(1)	a9(3)	a10(4)
e(i)	0	0	0	3	3	2	2	6	7	5

---

④：求l(i)的值（活动最晚开始时间）

1. l ( i )：活动ai是由弧< vk,vj >表示，则ai的最晚发生时间要保证vj的最迟发生时间不拖后（vj最迟发生时间为9的话，ai的最迟时间就必须是 9-活动耗时 ）。因此，l(i)=vl(i)-len< vk,vj >
   即：活动到达顶点的最晚发生时间减去边的权重

边	a1(3)	a2(6)	a3(2)	a4(4)	a5(2)	a6(1)	a7(3)	a8(1)	a9(3)	a10(4)
l(i)	0	0	1	3	4	5	3	6	7	6

---

⑤：求出关键边和关键路径:

1. 当e(i)==l(i)，即：活动最早开始时间 = 活动最晚开始时间时，可以得到关键边为：
   a1 a2 a4 a8 a9

2. 然后根据关键边组合成关键路径：
   a1->a4->a9 和 a2->a8->a9