爲什麼關鍵路徑的權重提供了執行所有工作的總時間的下限？

Question

在算法導論P657，第3版，它說：

的關鍵路徑就是通過DAG中的最長路徑，對應於 最長的時間來執行作業的任何序列。因此，關鍵路徑的權重提供了執行所有工作的總時間的下限。

我明白了第一句話。但在第二句，它說

關鍵路徑提供了一個下界

爲什麼它提供了一個下界一個上限，而不是在執行所有作業的總時間？

我想我可能會誤解關鍵路徑？

Answer 1

在完成路徑中的以前作業之前，無法在關鍵路徑中啓動任何作業。因此，任何合法的時間表都將採用權重的總和來完成關鍵路徑上的所有工作。所以任何關鍵路徑都是完成所有工作的時間的下限。

（如果您始終有足夠的資源同時處理所有當前可開始的作業，那麼最長的關鍵路徑也將是完成所有作業的時間）。