如何使用一組開始點和目標點在圖中找到最長的路徑？

我有一個DAG（成本/權重每邊），並希望找到兩組節點之間的最長路徑。與圖中節點的總數相比，這兩組起始節點和目標節點是不相交的並且尺寸較小。如何使用一組開始點和目標點在圖中找到最長的路徑？

我知道如何在之間有效地做到這一點開始和目標節點。有了多個，我可以列出從每個開始到每個目標節點的所有路徑，並選擇最長的路徑 - 但這需要二次數的單一路徑搜索。有沒有更好的辦法？

來源

2015-04-02 starmole

http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/ – Techie 2015-04-16 07:35:55

這可能有用。 [DAG中最長路徑] [1] [1]：http://stackoverflow.com/questions/10712495/longest-path-in-a-dag – 2015-04-16 08:25:19

我假設你想要的最長路徑可能從第一組中的任何節點開始，到第二組中的任何節點結束。然後，您可以添加兩個虛擬節點：

的第一個節點沒有前輩和它的後繼者是從第一組中的節點。
第二個節點沒有後繼者，其前輩是第二個集合中的節點。

所有新添加的邊都應該具有零權重。

該圖仍然是一個DAG。現在，如果使用標準算法在兩個新節點之間查找DAG中最長的路徑，則將獲得最長的路徑，該路徑從第一個集合開始到第二個集合結束，除了將會有一個額外的零 - 在開始時加權的邊緣和在結尾處的額外的零加權邊緣。

順便說一下，這個解決方案本質上是從第一組中的所有節點執行算法，但是並行執行，而不是您的問題提出的順序方法。

來源

2015-04-12 22:38:22 Palec

我希望我沒有接受過答案早期，因爲直觀上，這有很大的意義，並且非常簡單！另一方面，我仍然想用暴力解決方案來測試它。但據我所知，這將完全奏效！謝謝！ – starmole 2015-04-17 02:02:22

如果我的解決方案很明顯，唯一可能出錯的是性能。拓撲排序在圖的大小（節點+邊）上需要線性時間，所以兩個添加的節點具有幾條邊幾乎沒有區別。如果一個節點位於從一個開始節點到一個結束節點的路徑上，那麼我的算法就會對它進行一次處理，一次是針對每對開始節點和結束節點之間的蠻力算法。另外我的解決方案只需要初始化和後處理一次，而蠻力算法需要爲每一對獲得實際候選最長路徑，以避免極端的內存消耗。 – Palec 2015-04-17 10:43:31

如何使用一組開始點和目標點在圖中找到最長的路徑？

回答

相關問題