C语言AOE网、关键路径_画aoe网

目录

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)}}$ ：活动 $a_{}i$ 的最早发生时间。$^{e_{(i)}}$ = Ve（j）。（活动 $a_{}i$ ：所有以Vj为起点的各条出边<Vj, Vk>表示的活动）

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

（4）$l_{(i)}$ ：活动 $a_{}i$ 的最迟开始时间。等于 $a_{}i$ 的最迟完成时间减去 $a_{}i$ 的持续时间：$l_{(i)}$ = Vl（k）-  dur（< j, k >）

（5）$d_{(i)}$ ：活动 $a_{}i$ 的时间余量。$d_{(i)}$ = $l_{(i)}$ - $^{e_{(i)}}$ 

（6）dur（< j, k >）：活动 $a_{}i$ 的持续时间（活动 $a_{}i$ ：边<Vj, Vk>表示的活动）

（7）关键活动：活动的时间余量为0的活动。即$d_{(i)}$ = $l_{(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$ （边<Vj, Vk>表示的活动）的最早发生、最迟开始时间 $^{e_{(i)}}$ 、$l_{(i)}$ 

$^{e_{(i)}}$ = Ve（j），$l_{(i)}$ = Vl（k）- dur（< j, k >）

（3）确定关键路径

首先：计算活动 $a_{}i$ 的时间余量$d_{(i)}$ = $l_{(i)}$ - $^{e_{(i)}}$ 

其次：找出$d_{(i)}$ = 0 的活动 $a_{}i$ 

所有$d_{(i)}$ = 0 的活动 $a_{}i$ 的路径集合即为AOE网中的关键路径。

2.4关键路径求解示例

 

       利用上述公式，计算如图所示的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$ 的最早开始时间 e(i)、最迟开始时间 l(i) 和时间余量 d(i)：

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