数据结构 — 图 之 关键路径、关键活动 (文字表述)
发布日期:2021-06-30 19:49:34
浏览次数:2
分类:技术文章
本文共 469 字,大约阅读时间需要 1 分钟。
1、AOE网:
边表示活动的网络,边表示活动,顶点表示事件,当该事件发生了,就说明触发该事件发生的所有的活动已经完成。一个工程所需的最短时间 就是 完成从开始顶点到终止顶点的最长路径的长度。
2、关键路径:
关键路径就是从开始顶点到结束顶点之间 一条具有最长路径长度的路径。关键路径可能不止一条。
3、活动的early(i):
一个事件(顶点vi)的最早发生时间 -> 最长路径的长度 -> early(i)活动ai的最早开始时间 -> vi 是 ai 开始的前提 -> vi最早完成时间
4、活动的late(i):
活动(边ai)最迟开始时间 -> 不增加工程工期的前提下,最多推迟几天 -> late(i)活动ai最迟开始时间 -> 工期 -( 该活动所需的时间 + 之后活动所需的时间和)
5、关键活动:
满足early(i) = late(i) 的活动,这足以说明该活动的关键程度。
6、确定关键路径的算法:
1)early(i) 2)late*(i) 3)得出关键活动 4)删除非关键活动 5)得到一条从开始顶点到终止顶点的路径
转载地址:https://lipenglin.blog.csdn.net/article/details/50061357 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年05月01日 03时39分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
记一次曲折的Debug经历
2019-04-30
Impala支持Google云存储开发笔记
2019-04-30
如何在Apache JIRA中搜索issue
2019-04-30
scrapy 排错记录
2019-04-30
ACM路上的一大失误
2019-04-30
HDOJ2049 不容易系列之(4)——考新郎
2019-04-30
CodeForces 248B - Chilly Willy - 找规律
2019-04-30
POJ-2418 Hardwood Species(Trie树)(map)
2019-04-30
HDU-4300 Clairewd’s message + 4333(扩展KMP)
2019-04-30
HDU 1592 Half of and a Half(高精度)
2019-04-30
POJ-3304 Segments(计算几何)
2019-04-30
UVA-11538 Chess Queen(数学)
2019-04-30
UVA-11401 Triangle Counting(数学优化)
2019-04-30
Codeforces Round #369 (Div. 2)
2019-04-30
UVA 11426 GCD - Extreme (II)(欧拉函数)
2019-04-30
HDU-2838 Cow Sorting(树状数组)
2019-04-30
POJ-2299 Ultra-QuickSort(树状数组)(离散化)
2019-04-30
基于SSM的兼职论坛系统的设计与实现
2019-04-30