如何在有向無環圖中找到'5'最重要的路徑？

Question

我有一個與每個節點相關的權重的有向無環圖（DAG）。我想找到最重要的'n'（例如5個）最重要的路徑，其中路徑的權重被定義爲它所有節點權重的總和。我怎樣才能做到這一點？

準確性是可取的，但可以犧牲性能。該圖可能具有10,000個以上的節點和/或邊緣。

編輯：權重將是大於或等於零的數字。

Answer 1

1. 拓撲排序圖。
2. 將每個圖的節點與n元素優先級隊列（min-heap）相關聯。
3. 對於每個節點（以排序順序），從優先級隊列中彈出路徑權重，添加節點的權重，並將它們傳遞給每個後代。當一個節點收到來自父節點的權重時，它應該將其插入關聯的優先級隊列中。
4. 對於每個葉子節點，來自優先級隊列的彈出路徑權重，添加節點的權重，並將它們插入到一個公共優先級隊列中。在處理完最後一個節點之後，此優先級隊列包含「n」個最重要路徑的權重。如果與重量一起存儲指針，則可以恢復這些路徑。