AOV、AOE都是有权无向图，AOV边不带权值，AOE带权值。

关键路径是AOE中，开始顶点到结束顶点的所有路径中，具有最大路径长度的路径成为关键路径，路径上的点是关键活动。

（1）关键路径如果有多条，至提高一条关键路径上的关键活动并不能缩短工期，必须要加快所有关键路径上的关键活动才能加快工期。

（2）关键路径只有一条，关键活动也不是无限制缩短，工期会无限缩短的，因为可能缩到一定程度，这个节点就不是关键活动了。

求解关键路径的主要步骤：

（1）求解ve()，求解每个节点（事件）的最早发生时间： 规定ve(0) = 0。 ve(n) = max(ve(n-1)+x1,ve(n-2)+x2) 能够到达n的所有路径中最大值。

（2）求解vl()，求解每个节点（事件）的最迟发生时间：规定vl(终点）= ve(终点)。vl=min(vl(n-1)-x1,vl(n-2)-x2) 能够返回n的所有路径中的最小值。

（3）求解e()，求解每个活动的最早开始时间。->活动a连接的两端的顶点的最早发生时间

（4）求解l()，求解每个活动的最迟开始时间。->活动a连接的两端的终点的最迟发生时间-活动a历经的时间。

（5）用e()-l()，找出等于0的点，等于0的路径就是关键路径。

关键路径为：a2,a5,a7. v1->v3->v5->v6

20题。无需将所有步骤都完成，因为可以直接看出。最终选择C

21 ，求解ve(),vl() e() l () ，将e() - l () = 0 可以看出所有关键路径。因此有三条，最终选择C。

AOE网示例图：

AOE网：在一个表示工程的带权有向图中，用顶点表示事件（如V0），用有向边表示活动（如<v0,v1> = a1），边上的权值表示活动的持续时间，称这样的有向图为边表示的活动的网，简称AOE网（activity on edge network）

源点：
在AOE网中，没有入边的顶点称为源点；如顶点V0

终点：
在AOE网中，没有出边的顶点称为终点；如顶点V3

AOE网的性质：
【1】只有在进入某顶点的活动都已经结束，该顶点所代表的事件才发生；

         例如：a1和a2活动都结束了，顶点V2所代表的事件才会发生。

【2】只有在某顶点所代表的事件发生后，从该顶点出发的各活动才开始；

         例如：只有顶点V1所代表的事件结束之后，活动a2和a4才会开始。

 
在AOE网中，所有活动都完成才能到达终点，因此完成整个工程所必须花费的时间（即最短工期）应该为源点到终点的最大路径长度。具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动：

 
事件的最早发生时间：ve[k]
根据AOE网的性质，只有进入Vk的所有活动<Vj, Vk>都结束，Vk代表的事件才能发生，而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以，计算Vk的最早发生时间的方法为：

ve[0] = 0

ve[k] = max(ve[j] + len<Vj, Vk>)

事件的最迟发生时间：vl[k]
vl[k]是指在不推迟整个工期的前提下，事件Vk允许的最迟发生时间。根据AOE网的性质，只有顶点Vk代表的事件发生，从Vk出发的活动<Vk, Vj>才能开始，而活动<Vk, Vj>的最晚开始时间为 vl[k]=vl[j] - len<Vk, Vj>。

活动的最早发生时间：ee[i]
ai由有向边<Vk, Vj>，根据AOE网的性质，只有顶点Vk代表的事件发生，活动ai才能开始，即活动ai的最早开始时间等于事件Vk的最早开始时间, ee[i] = ve[k]

活动的最迟发生时间：el[i]
el[i]是指在不推迟整个工期的前提下，活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后，即 el[i]=vj最迟发生时间-ai

案例：

原始AOE网：

事件的最早发生时间：ve[k]

从源点向终点方向计算

ve[0] = 0

ve[1] = ve[0] + a0 = 0 + 4 = 4

ve[2] = max( ve[0] + a1, ve[1] + a2 ) = max(0 + 3, 4 + 2 = 6

ve[3] = max(ve[1] + a4, ve[2] + a3) = max(4 + 6, 3 + 4) = 10

事件的最迟发生时间：vl[k]

从终点向源点方向计算

vl[3] = ve[3] = 10

vl[2] = vl[3] - a3 = 10 - 4 = 6

vl[1] = min(vl[3] - a4, vl[2] - a2) = min(10-6, 6-2) = 4

vl[0] = min(vl[2] - a1, vl[1] - a0) = min(4-4, 4-2) = 0 

活动的最早发生时间：ee[i]

共有五个活动：

ee[0] = ve[0] = 0

ee[1] = ve[0] = 0

ee[2] = ve[1] = 4

ee[3] = ve[2] = 6

ee[4] = ve[1] = 4

活动的最迟发生时间：el[i]

el[0] = v[1] - a0 = 4 - 4 = 0

el[1] = vl[2] - a1 = 6 - 3 = 3

el[2] = vl[2] - a2 = 6 - 2 = 4

el[3] = vl[3] - a3 = 10 - 4 = 6

el[4] = vl[3] - a4 = 10 - 6 = 4

活动的最早开始时间和最晚开始时间相等，则说明该活动时属于关键路径上的活动，即关键活动。

经过比较，得出关键活动有：a0, a2, a3, a4，画出示意图如下：

该AOE网有两条关键路径。

所以，通过此案例也可以发现，一个AOE网的关键路径可能有多条。