如何計算定向非循環圖的關鍵路徑？

Question

當圖的節點具有權重時，計算定向無環圖的關鍵路徑的最佳方法（關於性能）是什麼？

例如，如果我有以下結構：

  Node A (weight 3) 
      /   \ 
    Node B (weight 4)  Node D (weight 7) 
    /    \ 
Node E (weight 2) Node F (weight 3) 

關鍵路徑應該是A-> B-> F（總重量：10）

Answer 1

我不知道「關鍵線索路徑「，但我假設你的意思是this。

只有通過遍歷整棵樹然後比較長度才能找到帶有權重的非循環圖中最長的路徑，因爲您永遠不知道樹的其餘部分是如何加權的。你可以在Wikipedia找到更多關於遍歷樹的信息。我建議，你先進行預購遍歷，因爲它很容易和直接實施。

如果您要經常查詢，您可能還希望使用有關插入時子樹權重的信息來擴充節點之間的邊界。這是相對便宜的，而重複遍歷可能非常昂貴。

但是如果你不這樣做，那麼沒有什麼能夠真正的將你從完整的遍歷中拯救出來。順序並不重要，只要你做一個遍歷並且永遠不會走相同的路徑兩次。

Answer 2

我會用動態規劃解決這個問題。爲了找到從S到T中的最大成本：

• 拓撲圖的節點作爲S = X_0，X_1，...，x_n =排序T.（忽略，可以達到S或從任何到達節點T.）
• 從S到S的最大成本是S.的重量
• 假設您計算了從S到x_i的最大成本，對於所有i < k，從S到x_k的最大成本是成本的x_k加上邊緣到x_k的任何節點的最大成本。

Answer 3

嘗試A *方法。

A* Search Algorithm

最後，處理的葉子，只是讓所有的人都導致到最後一點，設定爲目標。

Answer 4

有一篇論文聲稱具有這樣的算法：「具有時間限制的活動網絡中的關鍵路徑」。可悲的是，我找不到免費副本的鏈接。短的，我只能第二種改性http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm或http://en.wikipedia.org/wiki/A *

UPDATE的想法：我的蹩腳的格式，服務器端降價發動機道歉顯然打破。

Answer 5

我的第一個答案，請原諒任何非標準的東西由文化的計算器。

我認爲解決方案很簡單。只是否定權重並運行DAG的經典最短路徑（當然，對頂點的權重進行修改）。它應該運行得相當快。（時間複雜度爲O（V + E）也許）

我認爲它應該當你抵消權重，最大的一個將變得最小，第二個最大的將是第二小的，等等，就好像a > b然後-a < -b 。然後運行DAG應該就足夠了，因爲它會找到解決方案的最小路徑的否定的一個，從而找到原來的最長路徑