——本节内容为Bilibili王道考研《数据结构》P67视频内容笔记。
目录
一、基本概念
1.AOE网
2.AOE网的性质
3.关键路径
4.最早最晚时间
二、求关键路径
1.步骤
2.举例
三、关键活动/路径特性
一、基本概念
1.AOE网
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动需要的时间），称之为用边表示活动的网络，简称AOE网。
（1）在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；
（2）也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
2.AOE网的性质
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
（2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生，另外有些活动是可以并行进行的。
3.关键路径
从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
4.最早最晚时间
（1）事件vk的最早发生时间ve(k)：决定了所有从vk开始的活动能够开工的最早时间；
（2）活动ai的最早开始时间e(i)：指该活动弧的起点所表示的事件的最早发生时间；
（3）事件vk的最迟发生时间vl(k)：指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间；
（4）活动ai的最迟开始时间l(i)：指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差；
（5）活动ai的时间余量：d(i)=l(i)-e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间；
（6）若一个活动的时间余量为0，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动ai是关键活动，由关键活动组成的路径就是关键路径。
二、求关键路径
1.步骤
（1）求所有事件的最早发生时间ve()；
（2）求所有事件的最迟发生时间vl()；
（3）求所有活动的最早发生事件e()；
（4）求所有活动的最迟发生时间l()；
（5）求所有活动的时间余量d()；
（6）d(i)=0的就是关键活动，所有关键活动组成的路径即为关键路径。
2.举例
三、关键活动/路径特性
1.若关键活动耗时增加，则整个工程的工期将增长；
2.缩短关键活动的时间，可以缩短整个工程的工期；
3.当缩短到一定程度时，关键活动可能会变成非关键活动；文章来源：https://www.toymoban.com/news/detail-726863.html
4.可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。 文章来源地址https://www.toymoban.com/news/detail-726863.html
到了这里，关于数据结构——关键路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
