👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏
AOE网
在带权有向图中，以 顶点表示事件，以 有向边表示活动，以 边上的权值表示完成该活动的开销（如完成活动所需要的时间），称之为用边表示活动的网络，简称 AOE网（Activity On Edge Network）
AOE网具有以下两个性质：
- 只有在某顶点代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
- 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
此外，有些活动是可以并行进行的
在AOE网中 仅有一个 入度为0的顶点，称为 开始顶点（源点） ，它表示整个工程的开始；
也 仅有一个 出度为0的顶点，称为 结束顶点（汇点），它表示整个工程的结束
关键路径
从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为 关键路径 ，而把关键路径上的活动称为 关键活动
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长
事件
v
k
v_k
vk 的最迟发生时间
v
l
(
k
)
vl(k)
vl(k) —— 它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
***活动
a
i
a_i
ai 的最迟发生时间
l
(
i
)
l(i)
l(i) ——它是指该活动弧的重点所表示事件的最迟发生时间与该活动所需时间的差
活动
a
i
a_i
ai 的时间余量
d
(
i
)
=
l
(
i
)
−
e
(
i
)
d(i)=l(i)-e(i)
d(i)=l(i)−e(i) ，表示 在不增加完成整个工程所需总时间的情况下，活动
a
i
a_i
ai 可以拖延的时间
由 关键活动 组成的路径就是 关键路径
求关键路径的步骤
- 求所有事件的最早发生时间 v e ( ) ve() ve()
- 求所有事件的最迟发生时间 v l ( ) vl() vl()
- 求所有活动的最早发生时间 e ( ) e() e()
- 求所有活动的最迟发生时间 l ( ) l() l()
- 求所有活动的时间余量
d
(
)
d()
d()
d ( i ) = 0 d(i)=0 d(i)=0 的活动就是关键活动，由关键活动可得关键路径
求所有事件的最早发生时间
按 拓扑排序 序列，依次求各个顶点的
v
e
(
k
)
ve(k)
ve(k) ：
v
e
(
源点
)
=
0
ve(源点)=0
ve(源点)=0
v
e
(
k
)
=
M
a
x
{
v
e
(
j
)
+
W
e
i
g
h
t
(
v
j
,
v
k
)
}
ve(k)=Max\{ve(j)+Weight(v_j,v_k)\}
ve(k)=Max{ve(j)+Weight(vj,vk)} ，
v
j
v_j
vj 为
v
k
v_k
vk 的任意前驱
求所有事件的最迟发生时间
按 逆拓扑排序 序列，依次求各个顶点的
v
l
(
k
)
vl(k)
vl(k) ：
v
l
(
汇点
)
=
v
e
(
汇点
)
vl(汇点)=ve(汇点)
vl(汇点)=ve(汇点)
v
l
(
k
)
=
M
i
n
{
v
l
(
j
)
−
W
e
i
g
h
t
(
v
k
,
v
j
)
}
vl(k)=Min\{vl(j)-Weight(v_k,v_j)\}
vl(k)=Min{vl(j)−Weight(vk,vj)} ，
v
j
v_j
vj 为
v
k
v_k
vk 的任意后继
求所有活动的最早发生时间
若边 < v k , v j > <v_k,v_j> <vk,vj> 表示活动 a i a_i ai ，则有 e ( i ) = v e ( k ) e(i)=ve(k) e(i)=ve(k)
求所有活动的最迟发生时间
若边 < v k , v j > <v_k,v_j> <vk,vj> 表示活动 a i a_i ai ，则有 l ( i ) = v l ( j ) − W e i g h t ( v k , v j ) l(i)=vl(j)-Weight(v_k,v_j) l(i)=vl(j)−Weight(vk,vj)
求所有活动的时间余量
d ( i ) = l ( i ) − e ( i ) d(i)=l(i)-e(i) d(i)=l(i)−e(i)
![![[Pasted image 20240706162010.png]]](https://i-blog.csdnimg.cn/direct/68771ed54a1442108698f30fd3db799e.png)
关键活动、关键路径的特性
- 若关键活动耗时增加，则整个工程的工期将延长
- 缩短关键活动的时间，可以缩短整个工程的工期
- 当缩短到一定程度时，关键活动可能会变成非关键活动
- 可能有多条 关键路径，只提高一条关键路径上的关键活动速度 并 不能 缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动 才能达到缩短工期的目的
