关键路径详解

你的名字 2022-06-10 13:29 178阅读 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 条评论，178人围观）

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

相关阅读

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

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

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

相关 AOE网上的关键路径

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

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

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

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

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

相关 AOE网上的关键路径

AOE网上的关键路径 Time Limit: 1000MS Memory Limi

心已赠人/ 2022年07月15日 08:36/ 0 赞/ 143 阅读

相关 AOE网上的关键路径

AOE网上的关键路径 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Probl

柔情只为你懂/ 2022年07月14日 03:46/ 0 赞/ 156 阅读

相关关键路径详解

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

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

相关关键路径计算

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

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

相关经典算法之关键路径

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

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

相关拓扑排序和关键路径

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

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

相关关键路径JS实现

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

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