DAG中的關鍵路徑和最長路徑是否有區別？

Question

在我看過的每本書中，他們都說關鍵和最長的路徑是一樣的。問題是，在關鍵路徑上，所有活動都必須是關鍵性的。如果我在尋找最長的路，我不會關注活動是否是關鍵。或者我沒有得到什麼？

Answer 1

考慮建模的一組序列化的，部分地相互依賴活動，其中，所述活動是由邊緣表示，並且由節點的相互依存關係的組成項目的曲線圖，使得2個邊緣e1，e2入射當且僅當e1活動必須之前完成活動e2可以開始。假設代表項目開始和結束的2個特殊頂點s,t，

在這樣一個模型中，關鍵路徑描述了一個不能相互平行的最大活動序列。

其名稱源於這樣一個事實，即關鍵路徑中恰好一個活動的任何延遲必然會延遲整個項目，而對於所有其他活動則會有一些緩衝時間可用。

特別是關鍵路徑不一定匹配那些對項目整體成功至關重要的活動。

關鍵路徑對應於圖中s,t之間的最長路徑。

當然，關鍵路徑不必是唯一的。

Answer 2

從http://en.wikipedia.org/wiki/Longest_path_problem

用於調度一組活動的關鍵路徑的方法包括 有向無環圖，其中 代表項目里程碑和邊緣上的頂點表示 必須之後進行活動的結構一個里程碑，在另一個之前;每個邊緣是 加權估計相應的活動將完成的時間量。在這樣的圖表中，從第一個里程碑到最後一個里程碑的最長路徑是關鍵路徑，其中 描述了完成項目的總時間。

他們引用了Sedgewick，Robert; Wayne，Kevin Daniel（2011），算法（第4版），Addison-Wesley Professional，第661-666頁。