题23

题23

题目

Q:
若某带权图为，其中,

注：边括号外的数据表示边上的权值，则 的关键路径的长度为()。
A. 19
B. 20
C. 21
D. 22

分析

A:对于关键路径这个东西还是不熟悉
关键路径是指 AOE 网中从起点到终点耗时最长的路径，它决定了整个工程的完成时间。
同时还需要满足一个原则就是，A指向B，那么A就必须在B之前完成
求关键路径的步骤如下：

1. 求所有点的最早开始时间 (VE)
   • 使用拓扑排序，从起点开始，依次遍历所有点。
   • 每个点的最早开始时间等于其所有入边指向的点的最早开始时间加上入边权重的最大值。
   • 
   • 每个点的最早开始时间初始值为 0。
   • 每次更新一个点的最早开始时间时，要与之前记录的该点最早开始时间比较，取最大值。
2. 求所有点的最晚开始时间 (VL)
   • 使用逆拓扑排序，从终点开始，依次遍历所有出度为0的点。
   • 每个点的最晚开始时间等于其所有出边指向的点的最晚开始时间减去出边权重的最小值。
   • 
   • 每个点的最晚开始时间初始值为终点的最晚开始时间。
   • 每次更新一个点的最晚开始时间时，要与之前记录的该点最晚开始时间比较，取最小值。
3. 求所有边的最早开始时间 (EE) 和最晚开始时间 (EL)
   • 每个边的最早开始时间等于其起始点的最早开始时间。
   • 每个边的最晚开始时间等于其终点的最晚开始时间减去边权重。
4. 确定关键活动
   • 找出所有满足 EE = EL 的活动，这些活动即为关键活动。
   • 
5. 确定关键路径
   • 将所有关键活动连接起来，形成一条从起点到终点的路径，这条路径即为关键路径。
   • 
     注意：

• 关键路径可能不唯一。
• 关键活动是不能拖延的活动，因为它们决定了整个工程的完成时间。
• 非关键活动可以有一定的时间余量，即可以拖延一定的时间，但不能超过其时间余量。

解

C
题目描述的图如下, 得到关键路径的长度为 21 , 图中画出的两条路径都是关键路径。