关键路径详解

你的名字 2022-06-10 13:29 213阅读 0赞

在这里我们引入AOV（Activity-On-Edge）网概念，用顶点表示事件，用边来表示活动。区别于AOV网，AOE网的边是有权值的，代表完成事件的时间。

你需要先了解拓扑排序的有关知识。具体详见博文：http://blog.csdn.net/lee18254290736/article/details/77430334

![Center][]

在这里引入几个概念：

起始点称作源点

终止点称作汇点

针对顶点事件：事件最早完成时间Ve（k），事件最晚完成时间Vl（k）。

针对边上的活动：活动最早完成时间e（i），活动最晚完成时间l（i），关键路径，关键活动。

关键活动指的是l（i）-e（i）=0的一个活动，关键路径指的是由关键活动组成的由起始点到终点的完整路径。

求解事件，活动最早完成时间步骤：

规定源点事件第一天的开始时间为0， 即入度为0的顶点。

活动<V1,V2>所需时间为2，故事件2最早完成时间为2。

所以有以下推论：

Ve(1) = 0

Ve(2) = 2

Ve(3) = 5

Ve(4) = 6

在讨论事件5最早发生时间的时候，需要前面两条路径的时间都完成才可以。耗费时间最长的是2-3-5，则需要等待2-3-5完成才可以。即Ve（5）=10.所以有公式

Ve\[i\] = Max \{ max \[ Ve（i） \] + dur(i,j)   |   dui(i,j)为节点i到节点j的时间\] \}

由此可知：

Ve(5) = 10

Ve(6) = 13

Ve(7) = 16

Ve(8) = 17（同Ve（4）的求法）

我们规定最后一件事件的最晚完成时间与最早完成时间相同。即Ve(7) = Vl(7) = 17.

事件最晚完成时间求解步骤：

将完成的17天扣掉活动所需时间，就是事件最晚的完成时间。

Vl（7） = 17

Vl（6） = 16

Vl（5） = 10

Vl（4） = 8

Vl（3） = 5

Vl（2） = 2

Vl（1） = 0

事件5与事件2的最晚完成时间如何确定？

在事件5与2之后有两条路径，一个权值长，一个权值少。我们选择权值长的。

Vl(j) = Min\{vl\[k\] - dur\[j,k\]\}

剩下的之后再补上

[Center]: /images/20220610/0f9230d1fc47499cbd23e5a320ac44db.png

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】什么的图的关键路径？关键路径相关概念？关键路径算法实现？

目录一、什么是关键路径？ 1、现实问题二、关键路径相关概念？三、关键路径算法实现？ 1、算法分析 2、算法步骤 3、算法实现 ------------

朴灿烈づ我的快乐病毒、/ 2023年09月26日 10:28/ 0 赞/ 14 阅读

相关关键路径上找时间，非关键路径上找资源

项目在执行的过程中，必然会出现问题，有些时候是因为资源不够，资源调配出现问题，有些时候是因为项目估算时间出现了问题，或者项目中出现了未能够预测到的风险，而这些都

ゞ浴缸里的玫瑰/ 2023年02月23日 05:14/ 0 赞/ 22 阅读

相关关键路径(防止题目重复)

DAG(Directed AcyclineGraph) 有向无环图用来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只有完成了这些子工程，就可以

超、凢脫俗/ 2022年12月18日 13:57/ 0 赞/ 197 阅读

相关 AOE网上的关键路径

AOE网上的关键路径 Time Limit: 1000MS Memory limit: 65536K 题目描述一个无环的有向图称为无环图（Direc

蔚落/ 2022年08月14日 05:47/ 0 赞/ 183 阅读

相关数据结构----关键路径详解

前言 Live beautifully, dream passionately, love completely. Name：Willam Time：2017/3/

分手后的思念是犯贱/ 2022年07月16日 00:46/ 0 赞/ 227 阅读

相关关键路径详解

在这里我们引入AOV（Activity-On-Edge）网概念，用顶点表示事件，用边来表示活动。区别于AOV网，AOE网的边是有权值的，代表完成事件的时间。你需要先了解拓扑

你的名字/ 2022年06月10日 13:29/ 0 赞/ 214 阅读

相关关键路径计算

转自http://blog.csdn.net/wang379275614/article/details/13990163 认识AOE网　　有向图中，

偏执的太偏执、/ 2022年06月09日 10:11/ 0 赞/ 199 阅读

相关经典算法之关键路径

问题提出：设一个工程有11项活动，9个事件，事件V1 ----- 表示整个工程开始，事件V9 ----- 表示整个工程结束。每个事件的开始必须是它之前的活动已完成。

末蓝、/ 2022年05月19日 02:48/ 0 赞/ 184 阅读

相关拓扑排序和关键路径

一：拓扑排序前面讲过拓扑排序只是简单的描述，下面具体的实现。用顶点表示活动，用弧表示活动间的优先关系的有向图为AOV网。 AOV网中没有环，检测的办法是进行拓扑排

Dear 丶/ 2022年04月03日 05:54/ 0 赞/ 225 阅读

相关关键路径JS实现

我勒个去，毕业论文终于提交了，赶紧完成图基本算法的最后一节。。。 1 定义在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时

迷南。/ 2022年03月29日 09:52/ 0 赞/ 191 阅读