如何设计CPM算法？

Question

如何表示具有列表数据结构的图我有三个类(图、节点、边缘)，并希望在图中找到关键路径。

如何计算

• ES :最早开始
• 教统会:最早完成
• LS :最新开始
• 立法会:最新完成

谢谢

Answer 1

另一种存储图形的方法是Boost图库(Boost graph，BGL)。据我在维基百科上看到的，临界路径是两个顶点之间最长的路径。此外，似乎在一般情况下找到最长路径是NP完全的，但是对于有向无圈图(DAG)，我认为这是您的情况，有更有效的算法。

最长路径算法不在BGL中，但是wikipedia上的DAG算法看起来相当容易实现。

Answer 2

优秀的快速图库有用于描述图的类和大量的图算法，包括最短路径。你也许能做这样的事。

然而，你似乎想要的实际上比标准的图形算法要复杂得多；似乎你想要微软项目的核心在一个简单的算法中可用，不幸的是它不是。您可能会考虑购买项目的副本，并使用它的COM API来创建您的计划--这可能是一种简单的方法，这取决于您的环境。不过，我想你还会有一大堆工作要做。