代码之家 › 专栏 › 技术社区 › L H

DAG中的关键路径和最长路径之间有什么区别吗?

directed-acyclic-graphs graph-algorithm

4

L H · 技术社区 · 11 年前

在我看的每一本书中,他们都说关键路径和最长路径是一样的。问题是,在关键路径上,所有的活动都必须是关键的。如果我在寻找最长的路径,我就不会关注活动是否至关重要。或者我什么都没得到?

2 回复 | 直到 11 年前

1

2

collapsar 11 年前

考虑一个图形建模项目,该项目由一组可序列化的、部分相互依赖的活动组成,其中活动由边表示,相互依赖由节点表示,使得2条边 e1 , e2 当 电子1 活动必须在活动之前完成 第2页 可以启动。假设2个特殊顶点 s , t 分别表示项目的开始和结束。

在这样的模型中,关键路径描述了不能相互并行的最大活动序列。

它的名字来源于这样一个事实,即关键路径上某一活动的任何延迟都必然会延迟整个项目,而所有其他活动都有一些缓冲时间。

特别是关键路径不一定与那些对项目的整体成功至关重要的活动相匹配。

关键路径对应于 s , 吨 在图中。

当然,关键路径不一定是唯一的。

2

0

Adam Burry 11 年前

安排一组活动的关键路径方法包括一个有向无环图的构造表示项目里程碑,边缘表示活动必须在一个里程碑之后和另一个里程碑之前执行;每个边缘通过对相应时间量的估计进行加权活动需要完成。在这样的图中,从最后一个里程碑的第一个里程碑是关键路径描述了完成项目的总时间。

他们引用了Sedgewick,Robert;Wayne,Kevin Daniel(2011),《算法》(第4版),Addison Wesley Professional,第661666页。