如何查找DAG中兩個頂點之間的最大權重路徑？

Question

在DAG G中，具有非負加權邊，您如何找到G中兩個頂點之間的最大權重路徑？

謝謝你們！

Answer 1

簡單的蠻力算法可以用遞歸函數編寫。 從一個空向量開始（在C++中：std :: vector）並插入第一個節點。 然後調用您的遞歸函數與向量的論點，即執行以下操作：

• 遍歷所有的鄰居，每個鄰居
  • 複製載體
  • 添加的鄰居
  • 叫我們自己

此外，將總重量作爲參數添加到重複sive功能並在每次遞歸調用中添加權重。

該函數應該在到達末端節點時停止。然後比較總重量和目前爲止的最大重量（使用全局變量），如果新的總重量較大，則設置最大重量並存儲矢量。

其餘的由你決定。

Answer 2

您可以使用拓撲排序在O（n + m）時間（其中n是節點的數量，m是邊的數量）中解決此問題。首先在反向圖上進行拓撲排序，這樣就可以使所有節點排序，以便在訪問所有子節點之前不會訪問任何節點。

現在，我們將使用該節點開始的權重最高的路徑的權重來標記所有節點。這是基於完成以下遞歸觀察：

• 從宿節點（沒有出邊的任何節點）開始的最高重量路徑的重量是零，因爲從該節點出發的唯一路徑是隻有該節點的長度爲零的路徑。
• 從任何其他節點開始的權重最高的路徑的權重由沿着出站邊緣到節點形成的任何路徑的最大權重給出，然後從該節點獲取最大權重路徑。

因爲我們有反向拓撲排序的節點，我們可以訪問所有的節點，在保證訂單，如果我們曾經嘗試以下的邊緣並在端點查找最重的路徑的成本節點，我們將已經計算出從該節點開始的最大權重路徑。這意味着，一旦我們有反向拓撲排序的順序，我們可以採用如下算法到所有節點的順序：

1. 如果該節點沒有出邊，記錄開始那最重的路徑的權重節點（表示爲d（u））爲零。否則，對於離開當前節點u的每個邊（u，v），計算l（u，v）+ d（v），並將d（u）設置爲這樣獲得的最大值。

一旦我們完成了這一步，我們可以在所有節點上進行最後一遍，並返回任何節點獲得的最高值d。

該算法的運行時間可以分析如下。計算拓撲排序可以使用許多不同的方法在O（n + m）時間完成。當我們隨後掃描每個節點和每個節點的每個傳出邊緣時，我們只訪問每個節點和邊緣一次。這意味着我們在節點上花費O（n）時間，在邊上花費O（m）時間。最後，我們花費O（n）時間對元素進行最後一遍遍歷，以找到最高權重路徑，這需要O（n）。這給出了O（n + m）時間的總和，其與輸入的大小成線性關係。