数据结构vl怎么求_数据结构图之关键路径

作者：Cpp五条 | 2024-03-17 22:07:07

踩

图顶点的ve,vl

简单有向图.png

网络

AOV网络：有向图，用顶点表示活动，用弧表示活动的先后顺序

AOE网络：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间

名词解释

活动：业务逻辑中的行为，用边表示

事件：活动的结果或者触发条件

关键路径：具有最大路径长度(权重)的路径，可能不止一条

活动的两个属性：

e(i)表示最早开始时间

l(i)表示最晚开始时间

事件的两个属性：

ve(j)最早开始时间

vl(j)最晚开始时间

在下面的计算过程中，就可以理解这些属性的概念了

计算关键路径的过程

原理：

先求出每个顶点的ve和vl值

通过这两个值就可以求出每条边的e和l值。

取e(i)=l(i)的边就是关键路径上的边，关键路径不止一条

简单有向图.png

一、求ve(i)的值

从前向后，直接前驱节点的ve值＋当前节点的边的权值(有可能多条，取最大值)

第一个顶点的ve等于0

ve(1) = 0

ve(2) = ve(1) + len(a1) = 0 + 3 = 3

ve(3) = ve(1) + len(a3) = 0

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/258285

数据结构vl怎么求_数据结构 图之关键路径