从零开始学数据结构系列之第四章《什么是关键路径》

定义

​   从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

图解

那什么是关键路径？

​ 那我们做一个例子，老师叫3个人写作业，然后呢，如果他们3个都写完的话，让学委去收，

​   那我假设同学 a 写这次作业要一个小时，

​     同学 b 要3个小时

​     同学 c 要5个小时

​   那这样是不是我同学 a 同学 b 要等同学 c 都写完了之后的话，我学委才能把这三本作业给收齐，那这样的话，我们的关键节点也就是我们的同学 c 也就是最长那写作业时间那一个

​   那同理，我们的工程项目也是同样的道理，那所以我们工程项目中所需要最长时间的工程时间的话，也就是我们的关键路径

注意以下名词：

（1）求所有事件的最早发生时间ve()；

（2）求所有事件的最迟发生时间vl()；

（3）求所有活动的最早发生事件e()；

（4）求所有活动的最迟发生时间l()；

（5）求所有活动的时间余量d()；

事件最早开始时间

​   v–顶点，e–early）事件最早发生时间，指能够保证该事件一定发生的最早时间，对应最长路径。唯有保证该条路径最长，才能保证其他短的路径已经完成，该事件才会发生。

​   那我们可以拆分开来看，那我们可以将最早开始时间拆分成3个部分来进行理解

​   “最早” ---------- 可以理解成工程项目必须要在多少点前开始，如果工程并没有拖延的情况下，不在这个点开始的话，那工程项目就做不完了

​     ”开始“ --------- 工程开机时刻

​     ”时间“ ---------- 某一时刻

那我们还是拿上面的例子用来讲解

那假设教师要求一定要在五点钟前收齐作业

​   那我们 a 同学要开工的时间是4点

​   那我们 b 同学要开工的时间是2点

​   那我们 c 同学要开工的时间是12点

​   那12点 比 2 点要早 比 4 点要早，那我们 c 同学要开工的时间，就是我们的最早开始时间

​   那从上面我们可以得出相应的结论。那也就是说我们时间最长/值最大的这一条活动，也就是我们的最早开始时间

那我们可以根据下面的图来进行一个相应的判断

Ve（i）是我们的事件最早开始时间

那我们的最早开始时间的话，就是我们的正序拓扑结构

• 那首先我们 v 1节点到 v 1节点的话，那它的最早开始时间是一个0,（因为自己到自己的情况下并不需要花费时间，可以进行这样的理解），所以我们的 v 一的最早开始时间就是0

• 那看到我们 v2，那我们 v2的话是由只有我们 v 1节点才能到 v2节点。那我们的最早开始时间就是 v 1到 v2的活动时间也就是等于3

• 那同理我们 v3节点也是只能是 v 1节点到 v3节点，那也是我们的活动时间，那我们 v3的最早开始时间也就是2

• 那现在看到我们 v4节点,那到达我们 v4节点的话，可以由我们的 v2节点和 v3节点同时到达我们的 v4节点。那所以的话我们要看它的权值是哪边大哪边小，我们可以看到 v2和 v3节点它的活动时间，分别是2和4，分别对应这V1到V2到V4这样子，也是v 1到 v3到 v4这样子，那这两种情况的话，它的最早开始时间分别对应着3加2等于5与上2+4等于6，那我们的6是比5大的那所以根据我们前面的结论，那我们V4的最早开始时间的话就是6

• 那V5的话，那它的最短路径就是我们 v 1到 v2之后再到 v5。那这样的话，那我们的活动时间加起来的话，它就等于6，那我们 v5的最短路径就是6了

• 那同理的话，我们V6节点，我们可以通过 v5和 v4和 v3节点同时到达我们 v6节点。那根据我们这3个的最早开始时间，那开始计算，我们可以计算出它的结果是7，8，5，那v6的最短最早开始时间，那就是8。

事件最迟开始时间

​   事件最迟发生时间，指该事件可以发生的最晚时间，对应到最终顶点的最短距离。有一些事件与其他事件并行时，因为其他事件所在路径时间更长，所以该事件可以延迟发生。

那我们还是拿上面的例子用来讲解

那假设教师要求一定要在五点钟前收齐作业

​  那我们 a 同学要开工的时间是4点

​   那我们 b 同学要开工的时间是2点

​   那我们 c 同学要开工的时间是12点

​   那 4 点 比 2 点要晚 比 12 点要晚，那我们 A 同学要开工的时间，就是我们的最迟开始时间

​   那从上面我们可以得出相应的结论。那也就是说我们时间最长/值最小的这一条活动，也就是我们的最晚开始时间

Vl（i）是我们的最晚开始时间

  同理那我们的最晚开始时间的话，就是我们的逆序拓扑结构，也就是后往前看，如果有两条活动轨迹以上的话，那我们选择最小的一方来为我们的最晚开始时间

• 那由于我们的 v 一节点和 v6节点分别是开始以及结束。那它的最晚开始时间的话，就是它本身也就是不用变动，那就是分别是0和8
• 那我们看 v2节点，那它是可以通过 v6到 v5到 v2，或者就是 v6到 v4再到 v2这样子的步骤来走的，那它两边分别的活动时间都是4，那V2他的最晚开始时间的话，就是4
• 那我们 v3的话，它是可以 v6直接到 v3，或者是 v6到 v4再到 v3，那我们 v6到 v3的话，那它就是8-3=5。那如果是经过 v4节点的话，那它就是6-4=2，那这样的话我们从 v3来考虑，如果直接从 v3到 v6的话，那它就做不完了。那所以说我们要选取最小的，也就是我们 v4到 v6这个节点，所以我们逆序来看的话，那也是选取它活动轨迹最小的一条，来作为我们最晚开始时间，所以根据上一季的结论的话，我们可以得出我们 v3节点的最晚开始时间就是2.
• 那我们 v4也同理，我们可以直接从 v6直接到 v4，只有这一条活动轨迹，那这样的话就是8-2，那是等于6的，那所以我们 v4的最晚开始时间，那就是6
• 同理，那我们 v5的最短时间那就是8减去1，那是等于7

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
67【第四章】《拓扑排序介绍及其方法》
68【第四章】《拓扑排序代码详解》