如何設計CPM算法？

Question

如何用列表數據結構表示圖我有三個類（圖，節點，邊），並希望在圖中找到關鍵路徑。

如何計算

• ES：最早開始
• EC：最早完成
• LS：最遲開始
• LC：最新完成

感謝

Answer 1

存儲圖的另一種替代方法是Boost Graph Library（BGL）。從我在維基百科看到的，critical path是兩個頂點之間最長的路徑。此外，對於一般情況，找到longest path似乎是NP完全，但是對於有向無環圖（DAG），我認爲您的情況是，有更高效的算法。

最長路徑算法不在BGL中，但維基百科上的DAG算法看起來相當容易實現。

Answer 2

的優秀的quickgraph庫有用於描述圖的類和大量的圖算法，包括shortest path。你也許可以做那樣的事情。

雖然，你似乎想要的實際上比標準圖算法更復雜;似乎你想要一個簡單的算法提供Microsoft Project的核心，不幸的是它不是。您可能會考慮購買一個項目副本，並使用它的COM API來創建您的計劃 - 這可能是簡單的方法，具體取決於您的環境。不過，我懷疑你會面臨一大堆工作。