如何设计CPM算法？
如何用列表数据结构表示图我有三个类（图、节点、边），并且想找到图中的关键路径。
如何计算
- ES：最早开始
- EC：最早完成
- LS：最晚开始
- LC：最晚完成
谢谢
how to represent a graph with list data structure i have three class (Graph, Node, Edge) and would like to find the critical path in graph.
how to calculate
- ES : Earliest Start
- EC : Earliest Complete
- LS : Latest Start
- LC : Latest Complete
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
存储图形的另一种选择是 Boost 图形库 ( BGL）。从我在维基百科上看到的，关键路径是两个顶点之间的最长路径。此外，似乎找到最长路径对于一般情况来说是NP完全的，但对于有向无环图（DAG），我认为这是你的情况，有更有效的算法。
最长路径算法不在 BGL 中，但维基百科上的 DAG 算法看起来相当容易实现。
Another alternative for storing the graph is the Boost Graph Library (BGL). From what I see at wikipedia, the critical path is the longest path between two vertices. Furthermore it seems like finding the longest path is NP Complete for the general case but for a directed acyclic graph (DAG), which I think is your case, there are more efficient algorithms.
The longest path algorithm isn't in BGL but the DAG algorithm on wikipedia looks reasonably easy to implement.
优秀的quickgraph库有用于描述图的类，以及大量的图算法，包括最短路径。你或许可以做类似的事情。
然而，您似乎想要的实际上比标准图算法更复杂；似乎您希望以简单的算法提供 Microsoft Project 的核心，但不幸的是事实并非如此。您可能会考虑购买项目的副本，并使用它的 COM API 来创建您的计划——这可能是简单的方法，具体取决于您的环境。不过，我怀疑您还有一大堆工作要做。
The excellent quickgraph library has classes for describing graphs, and a large number of graph algorithms, including shortest path. You may be able to do something like that.
What you seem to want, though, is actually more complex than a standard graph algorithm; it seems like you want the core of Microsoft Project available in a simple algorithm, and unfortunately it's not. You might consider buying a copy of project, and using it's COM API to do create your plan -- that may be the easy way, depending on your environment. I suspect you're going to have a whole bunch of work ahead of you, though.