直接非循環圖中最長的路徑

Question

如何在沒有權重的情況下找到DAG中最長的路徑？

我知道如果DAG是拓撲排序的，從A到B的最長路徑可以在線性時間中找到，但是我需要在所有圖中找到最長的路徑。有沒有什麼比搜索所有頂點對之間最長路徑（這將是O（n^3））更快的方法？

Answer 1

這與尋找關鍵路徑相同。

有一個簡單的O（n）的DP解決方案：

• 拓撲的頂點進行排序。
• 對於每個頂點i，我們將記錄earliest(i)，最早可能的開始時間（對於所有頂點最初爲0）。按拓撲排序順序處理每個頂點i，每當earliest(i) + length(i, j) > earliest(j)時更新（增加）earliest(j)任何後繼頂點j的i。

完成此操作後，所有頂點上的最大值earliest(i)將是關鍵路徑（最長路徑）的長度。你可以通過從這個頂點向後追蹤來構造一個（通常可能有多於一條）最長路徑，查看它的前輩，看看它們中的哪些可能產生它作爲後繼（即它們中的哪些具有earliest(i) + length(i, j) == earliest(j)），迭代直到你沒有前輩擊中一個頂點。