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

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

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

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

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

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

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

从…起 http://en.wikipedia.org/wiki/Longest_path_problem

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

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