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网。如下图AOE网中，有10个事件，15个活动。


AOE网对比AOV网：
（1）AOV网的有向边不考虑权值，而AOE网的有向边考虑权值；
（2）AOV网的入度为0的顶点可以有多个，而AOE网入度为0的顶点只有一个；
（3）AOV网的出度为0的顶点可以有多个，而AOE网出度为0的顶点只有一个；
（4）AOV与AOE网都不允许出现环路。
AOE网具有如下性质：
（1）只有在进入某一顶点的各条有向边代表的活动结束后，该顶点所代表的事件才能发生；
（2）只有在某个顶点代表的事件发生后，从该顶点出发的各条有向边所代表的活动才能开始；
（3）在一个AOE网中，有一个入度为0的事件，称源点，它表示整个工程的开始。同时，有一个出度为0的事件，称汇点，它表示整个工程的结束。
AOE网的研究目标：
（1）完成整个工程需要多少时间？
（2）哪些活动是影响工程进度的关键？
基本概念：
路径长度：AOE网的一条路径上所有活动的总和称为该路径的长度。
关键路径：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。
关键活动：关键路径上的活动称为关键活动。
显然，完成整个工程的最短时间就是AOE网中关键路径的长度。
必要说明：为什么最短时间是最大路径长度？
拿上图说明，以事件v0为起点，0时开始（以秒为单位）。当时间过去5秒活动a1结束，事件v1发生，而此时，活动a2还差两秒才结束；再过3秒活动a3结束，但此时事件v3还不能发生，因为活动a4刚进行1秒还没有结束，必须再等5秒a4结束，事件v3才能发生。
所以，可以得出某一事件的发生，最早也要等前面的所有活动中最消耗时间（即路径最长）的那个活动完成。
当一个工程计划用AOE网表示后，所关心的问题就是如何找出关键路径上的关键活动，从而增加关键活动的投入，缩短关键活动持续时间，进而争取整个工程的提前完成。
参数定义（假设有n个结点），并对上图AOE网进行计算：


活动持续时间dut(<j，k>)：代表有向边（活动）<j，k>的权值。
事件可能的最早开始时间ve(k)：对于顶点vk代表的事件，ve(k)是从源点到该顶点的最大路径长度。递推公式：ve(0)=0；ve(k)=Max{ve(j)+dut(<j,k>)}，由公式，我们从源点v0正向计算。
事件允许的最晚发生时间vl(k)：对于顶点vk代表的事件，vl(k)是在保证按时完成整个工程的前提下，该事件最晚必须发生的时间。递推公式：vl(n)=ve(n)；vl(k)=Min{vl(j)-dut(<k,j>)}，由公式，我们从汇点v9反向计算。
活动可能的最早开始时间e(i)：对于有向边ai代表的活动，e(i)是该活动的狐尾事件可能的最早发生时间。
活动允许的最晚开始时间l(i)：对于有向边ai代表的活动，l(i)是该活动的弧头事件允许的最晚发生时间减去该活动持续的时间。
每个活动允许的时间余量就是l(i)-e(i)，而关键活动l(i)-e(i)=0，即可能的最早开始时间等于允许的最晚开始时间。
对于上面的AOE网图，把求解的各参数陈述于下表中：

事件
v0
v1
v2
v3
v4
v5
v6
v7
v8
v9
ve(k)
0
5
7
13
17
18
23
22
26
31
vl(k)
0
10
7
13
17
20
23
22
28
31
活动
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
e(i)
0
0
5
7
7
13
13
13
17
17
18
23
23
22
26
l(i)
5
0
10
7
14
13
15
19
17
17
20
26
23
22
28

由表1，整个工程需要的最少时间为ve(v9)=31。
由表2，根据条件l(i)-e(i)=0，得到关键活动有a2，a4，a6，a9，a10，a13，a14；从源点v0到汇点v9的只要经过关键活动的路径就是关键路径，所以该图的关键路径为（v0，v2，v3，v4，v6，v9）和（v0，v2，v3，v4，v7，v9）。
寻找关键活动的算法：
（1）建立包含n+1个顶点（这样是为了方便n直接代表下标）、e条有向边的AOE网。其中，顶点v0为源点，顶点vn为汇点。
（2）根据有向图的拓扑排序算法，求出AOE网的拓扑序列。如果存在环，拓扑序列不存在，则无法得到关键活动，算法失败退出。
（3）从源点v0开始，令源点v0的最早开始时间为ve[0]=0，按拓扑序列求其余各顶点k（k=1，2，···，n）的最早开始时间ve[k]。
（4）从汇点vn开始，令汇点vn的最晚发生时间vl[n]=ve[n]，按逆拓扑序列求其余各顶点k（k=n-1，n-2，···，0）的最晚发生时间vl[k]。
（5）计算每个活动的最早开始时间e[k]。
（6）计算每个活动的最晚开始时间l[k]。
（7）找出所有e[k]=l[k]的活动k，这些活动即为AOE网的关键活动。

数据结构AOE网关键路径问题，不算活动差，直接看事件最迟最早差，差为0的就是关键路径，这样做对么？

数据结构AOE网关键路径问题，不算活动差，直接看事件最迟最早差，差为0的就是关键路径，这样做对么？我做了几道6，7个点的简单题，得出的结论是和计算活动时间差的答案一样。既然一样为什么要计算活动的时间差呢？

不对，这个只是图比较简单，或者关键路径只有一条时可以

如果关键路径并行的比较多，光计算顶点就不行了，只能一条一条弧（有向边）去检验

https://zhidao.baidu.com/question/1992311184697397347.html

项目关键路径，在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）
 
对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（Critical Path），组成关键路径的活动称为关键活动。其通常做法是：
　　1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；
　　2） 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；
　　3） 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差；
　　4） 找出所有时差为零或者为负数的活动所组成的路线，即为关键路径；
　　5） 识别出准关键路径，为网络优化提供约束条件；
　　它具有以下特点：
　　1）关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。
　　2）关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。
　　3）关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会缩短项目工期；反之，则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间，也不至于影响工程的完工时间。
　　4）关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使关键路径发生变化。
　　5）可以存在多条关键路径，它们各自的时间总量肯定相等，即可完工的总工期。
　　关键路径是相对的，也可以是变化的。在采取一定的技术组织措施之后，关键路径有可能变为非关键路径，而非关键路径也有可能变为关键路径。
 
转载于:https://www.cnblogs.com/wanglei-xiaoshitou1/p/9914981.html