输入e条弧<j，k>，建立AOE网的存储结构；从源点v1出发，令ve(1)=0，求 ve(j)，2<=j<=n；从汇点vn出发，令vl(n)=ve(n)，求 vl(i)，1<=i<=n-1。
根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。
求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
扩展资料
在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。
而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。
关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。
参考资料来源：百度百科-关键路径法
参考资料来源：百度百科-关键路径
已赞过
已踩过<
柚鸥ASO
2024-03-16 广告
关键路径的计算方法如下：
（1） 输入e条弧<j,k>，建立AOE网的存储结构；
（2） 从源点v1出发，令ve(1)=0，求 ve(j) ,2<=j<=n；
（3） 从汇点vn出发，令vl(n)=ve(n)，求 vl(i), 1<=i<=n-1；
（4） 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。
求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。
扩展资料：
一、拓扑排序的执行
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
（1）选择一个入度为0的顶点并输出之；
（2） 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
二、关键路径相关术语
（1）AOE网
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。一个AOE网的关键路径可以不止一条。
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。
表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点和唯一的出度为0的完成顶点。
（2） 活动开始的最早时间e(i)；
（3） 活动开始的最晚时间l(i)；
（4） 事件开始的最早时间ve(i)；
（5） 事件开始的最晚时间vl(i)。
参考资料：百度百科-拓扑排序
参考资料：百度百科-关键路径
关键路径是项目管理中进度控制的一个术语。
在项目的网络图中，从项目开始到项目完成有许多条路径可以走，就像从798艺术区到北京大学一样（如图1）。如果20个人同时从798艺术区出发，每个人走不同的路(乘坐地铁、公交车或是自驾)，但只有20个人全部到达北京大学，才能完成聚会。这最后一个到达的人就是走最长路径（花费时间最多）的人。
图1
相似的，只有最长(花费时间最多)的路径完成之后，项目才算结束。这条在整个网络图中最长的路径就叫关键路径（critical path）。
上面先给大家一个关键路径的总体概念，下面我们来了解关键几个术语：
（1） 最早开始时间（ES）指某项活动最早能够开始的时间
（2） 最早结束时间 (EF) 指某项活动最早能够完成的时间
EF=ES+工期估计
EF是根据ES和工期估计，正向推算推算获得的。
（3） 最迟结束时间（LF） 指为了某项活动能够在要求的时间节点完成，最迟必须完成的的时间
（4） 最迟开始时间 (LS) 指为了某项活动能够在要求的时间节点完成，最迟必须开始的时间
LS=LF－工期估计
LS是根据LF和工期估计，反向推算获得的。
（5）总时差（TS）：项目EF和项目要求完成时间的差值,也成为浮动量（float）
总时差=LF－EF 或 总是差= LS－ES，两种计算方法得到的结果是相等的。
好，我们回来接着说关键路径，确定构成关键路径的一种方法是找出那些具有最小时差值的活动。用每项活动的LF－EF（ 或LS－ES，结果一样），然后找出最小值（要么是正时差最小，要么是负时差最大）的活动，则这些活动都是关键路径上的活动。
图2
其中，将时差累加，获得红线的时差最小，所以上图黄色线路为此项目的关键路径（如图2）。同时，任务D和任务E并行，任务D的时差为7天，而任务E的时差为8天，所以任务D有一天的浮动时间（如图3）。
图3
值得说明的是，如果项目很大，一个项目网络图从开始到结束会有很多条路径，一些路径可以总是正时差，另一些可能有负时差。那些具有正总时差的路径又是被称为非关键路径（noncritical paths），而那些总是差为0或是负值的路径被称为关键路径，在这种情况下，耗时最长的路径会被称为最关键路径（most noncritical paths）。
最后我们来总结一下关键路径法的4个关键点：
（1） 关键路径是项目网络图中最长的路径，他决定了项目的总耗时时间；
（2） 项目经理必须把注意力集中在那些优先等级较高的任务，确保他们准时完成，关键路径上任何活动的推迟都将导致整个项目推迟；
（3） 项关键路径要时间，向非关键路径要资源；
（4） 调整进度，平衡资源。
关键路径是项目管理中进度控制的一个术语。关键路径法的4个关键步骤：
（1） 关键路径是项目网络图中最长的路径，他决定了项目的总耗时时间；
（2） 项目经理必须把注意力集中在那些优先等级较高的任务，确保他们准时完成，关键路径上任何活动的推迟都将导致整个项目推迟；
（3） 项关键路径要时间，向非关键路径要资源；
（4） 调整进度，平衡资源。
关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。
在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。
