C语言AOE网、关键路径

淩亂°似流年 2022-04-25 04:46 245阅读 0赞

**目录**

1.AOE网（Activity On Edge Network）

1.1AOE网的概念

1.2AOE网两个顶点

2.关键路径

2.1关键路径的概念

2.2关键路径的几点说明

2.3关键路径的求解步骤

2.4关键路径求解示例

--------------------

## 1.AOE网（Activity On Edge Network） ##

### 1.1AOE网的概念 ###

若在带权的有向图中，用有向边表示活动（子工程），边上的权值表示活动持续时间，即完成该活动所需时间；用顶点表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此均已完成，它的所有出边活动就此开始这样一种状态，则成此带权的有向图为用边表示活动的网，简称AOE网。

### 1.2AOE网两个顶点 ###

（1）源点（起点）：表示整个工程的开始，只有出边，没有入边

（2）汇点（终点）：表示整个工程的结束，只有入边，没有出边

## 2.关键路径 ##

### 2.1关键路径的概念 ###

源点到汇点的所有路径中最长的路径长度（路径上各边的权值和）称为关键路径（Critical Path）。关键路径也指完成工程的最短时间。

### 2.2关键路径的几点说明 ###

（1）Ve（j）：时间Vj的最早发生时间，即源点V1到汇点Vj的最长路径长度

（2）![^\{e\_\{(i)\}\}][e_i] ：活动 ![a\_\{\}i][a_i] 的最早发生时间。![^\{e\_\{(i)\}\}][e_i] = Ve（j）。（活动 ![a\_\{\}i][a_i] ：所有以Vj为起点的各条出边<Vj, Vk>表示的活动）

（3）Vl（k）：事件Vk的最迟发生时间。等于汇点Vn的最早发生时间Ve（n）减去Vk到Vn的最长路径长度

（4）![l\_\{(i)\}][l_i] ：活动 ![a\_\{\}i][a_i] 的最迟开始时间。等于 ![a\_\{\}i][a_i] 的最迟完成时间减去 ![a\_\{\}i][a_i] 的持续时间：![l\_\{(i)\}][l_i] = Vl（k）-  dur（< j, k >）

（5）![d\_\{(i)\}][d_i] ：活动 ![a\_\{\}i][a_i] 的时间余量。![d\_\{(i)\}][d_i] = ![l\_\{(i)\}][l_i] - ![^\{e\_\{(i)\}\}][e_i]

（6）dur（< j, k >）：活动 ![a\_\{\}i][a_i] 的持续时间（活动 ![a\_\{\}i][a_i] ：边<Vj, Vk>表示的活动）

（7）关键活动：活动的时间余量为0的活动。即![d\_\{(i)\}][d_i] = ![l\_\{(i)\}][l_i] - ![^\{e\_\{(i)\}\}][e_i] = 0

### 2.3关键路径的求解步骤 ###

（1）计算事件Vj的最早、最晚发生时间Ve（j）、Vl（j）

从源点V1自左向右计算。Ve（1）= 0，Ve（j）= max\{ Ve（i）+ dur（< i, j >） \}

从汇点Vn自右到左计算。Vl（n）= Ve（n），Vl（j）= min\{ Vl（k）- dur（< j, k >） \}

（2）计算活动 ![a\_\{\}i][a_i] （边<Vj, Vk>表示的活动）的最早发生、最迟开始时间 ![^\{e\_\{(i)\}\}][e_i] 、![l\_\{(i)\}][l_i]

![^\{e\_\{(i)\}\}][e_i] = Ve（j），![l\_\{(i)\}][l_i] = Vl（k）- dur（< j, k >）

（3）确定关键路径

首先：计算活动 ![a\_\{\}i][a_i] 的时间余量![d\_\{(i)\}][d_i] = ![l\_\{(i)\}][l_i] - ![^\{e\_\{(i)\}\}][e_i]

其次：找出![d\_\{(i)\}][d_i] = 0 的活动 ![a\_\{\}i][a_i]

所有![d\_\{(i)\}][d_i] = 0 的活动 ![a\_\{\}i][a_i] 的路径集合即为AOE网中的关键路径。

### 2.4关键路径求解示例 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

利用上述公式，计算如图所示的AOE网中各事件发生的最早发生时间 Ve(i) 和最迟发生时间 Vl(i) ，所有活动的最早发生时间 e(i) 和最迟发生时间 l(i) ，确定关键路径并给出关键路径的长度。

求出图中所有事件的最早发生时间 Ve(i) 为：

Ve(1) = 0  
Ve(2) = Ve(1) + dur(<1,2>) = 0 + 6 = 6  
Ve(3) = Ve(1) + dur(<1,3>) = 0 + 4 = 4  
Ve(4) = Ve(1) + dur(<1,4>) = 0 + 5 = 5  
ve(5) = max\{Ve(2) + dur(<2,5>), Ve(3) + dur(<3,5>)\} = max \{6 + 1,4 + 1\} = 7  
Ve(6) = Ve(4) + dur(<4,6>) = 5 + 2 = 7  
Ve(7) = Ve(5) + dur(<5,7>) = 7 + 9 = 16  
Ve(8) = max\{Ve(5) + dur(<5,8>), Ve(6) + dur(<6,8>)\} = max\{7 + 7,7 + 4\} = 14  
Ve(9) = max \{Ve(7) + dur(<7,9>), Ve(8) + dur(<8,9>)\} = amax\{16 + 2,14 + 4\} = 18

求出图中所有事件的最早发生时间 Vl(i) 为：

Vl(9) = Ve(9) = 18  
Vl(8) = Ve(9) - dur(<8,9>) = 18 - 4 = 14  
Vl(7) = Ve(9) - dur(<7,9>) = 18 - 2 = 16  
Vl(6) = Ve(8) - dur(<6,8>) = 14 - 4 = 10  
Vl(5) = min\{Vl(8) - dur(<5,8>),Vl(7) - dur(<5,7>)\} = min\{14 - 7,16 - 9\} = 7  
Vl(4) = Vl(6) - dur(<4,6>) = 10 - 2 = 8  
Vl(3) = Vl(5) - dur(<3,5>) = 7 - 1 = 6  
Vl(2) = Vl(5) - dur(<2,5>) = 7 - 1 = 6  
Vl(1) = min\{Vl(2) - dur(<1,2>),Vl(3) - dur(<1,3>),Vl(4) - dur(<1,4>)\} = min\{6 - 6,6 - 4,8 - 5\} = 0

计算出图中所有活动 ![a\_i][a_i 1] 的最早开始时间 e(i)、最迟开始时间 l(i) 和时间余量 d(i)：

由上表可以看出，a1，a4，a7，a8，a10，a11 是关键活动。把AOE网的所有非关键活动删去，就可得到AOE网的关键路径，图中所有从源点到汇点的路都是关键路径。该AOE网的关键路径长度为18。

![20200308155309783.png][]

[e_i]: https://private.codecogs.com/gif.latex?%5E%7Be_%7B%28i%29%7D%7D
[a_i]: https://private.codecogs.com/gif.latex?a_%7B%7Di
[l_i]: https://private.codecogs.com/gif.latex?l_%7B%28i%29%7D
[d_i]: https://private.codecogs.com/gif.latex?d_%7B%28i%29%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220210/168b8e02824c449f9aaee3df2141bce7.png
[a_i 1]: https://private.codecogs.com/gif.latex?a_i
[20200308155309783.png]: /images/20220210/a2acab2fad3f46eaa6cc2e0ba6e019c1.png