在我看过的每一本书中，他们都说关键路径和最长路径是相同的。问题是，在关键路径上，所有活动都必须是关键的。如果我在寻找最长的路径，我不会关注活动是否关键。还是我什么都没有？
问问题
3366 次
2 回答
2
考虑一个图形建模一个项目，该项目由一组可序列化的、部分相互依赖的活动组成，其中活动由边表示，相互依赖由节点表示，例如 2 条边e1，如果必须在活动开始之前完成活动，e2则该活动是事件发生的。假设有 2 个特殊顶点，分别代表项目的开始和结束。e1e2st
在这样的模型中，关键路径描述了不能彼此并行化的最大活动序列。
它的名称源于这样一个事实，即关键路径上恰好一项活动的任何延迟都必然会延迟整个项目，而对于所有其他活动，则有一些可用的缓冲时间。
尤其是关键路径不一定与对项目整体成功至关重要的那些活动相匹配。
关键路径对应于图中 , 之间的最长s路径t。
当然，关键路径不必是唯一的。
于 2013-08-26T17:50:15.847 回答
0
From http://en.wikipedia.org/wiki/Longest_path_problem
The critical path method for scheduling a set of activities involves the construction of a directed acyclic graph in which the vertices represent project milestones and the edges represent activities that must be performed after one milestone and before another; each edge is weighted by an estimate of the amount of time the corresponding activity will take to complete. In such a graph, the longest path from the first milestone to the last one is the critical path, which describes the total time for completing the project.
They cite Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms (4th ed.), Addison-Wesley Professional, pp. 661–666.
于 2013-08-26T17:48:47.700 回答