关键路径怎么在短时间内计算出活动图中关键路径长度？如下图~求解！！！

关键路径时间:2021-08-16 阅读:()

什么是项目的关键路径？

关键路径法（Critical Path Method，CPM），又称为要径法，是计划项目活动中用到的一种算术方法。

[1] 对于有效的计划管理而言，关键路径是一个十分重要的工具。

与计划评核术（Project Evaluation and Review Techniqu，PERT）非常类似。

要径法所使用的估计作业时间是单一或确定的，而计划评核术则是使用机率性的估计作业时间。

这两种技术经常混合使用，简称CPM/PERT 。

关键路径通常(但并非总是)是决定项目工期的进度活动序列。

它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。

关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。

但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。

一个项目可以有多个、并行的关键路径。

另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。

最初，关键路径方法只考虑终端元素之间的逻辑依赖关系。

关键链方法中增加了资源约束。

数据结构里关键路径上的事件最早发生时间与最晚发生时间是否相同

不同。

事件最早发生时间ve（earliest time of vertex）：顶点vk的最早发生时间，从始点到vi的最长（加权）路径长度。

事件最晚发生时间vl(lastest time of vertex)：顶点vk的最晚发生时间，在不拖延整个工期的条件下，vi的可能的最晚发生时间。

A、从开始顶点 v1?出发，令 ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。

? Ve(k)=max{ve(j)+dut(<j,k>)} , j ∈ T 。

其中T是以顶点vk为尾的所有弧的头顶点的集合（2 ≤ k ≤ n）。

如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。

B、从完成顶点出发，令，按逆拓扑有序求其余各顶点的允许的最晚发生时间： vl(j)=min{vl(k)-dut(<j,k>)} ,k ∈ S 。

其中 S 是以顶点vj是头的所有弧的尾顶点集合（1 ≤ j ≤ n-1）。

扩展资料：优化关键路径是一种提高设计工作速度的有效方法。

一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。

在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。

EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。

参考资料来源：百度百科-关键路径