兩個頂點之間的最長路徑

我有一個加權邊的有向圖（權重都是正的）。兩個頂點之間的最長路徑

現在，我正在尋找一種有效的算法或代碼（特別是C＃）來查找兩個給定頂點之間最長的路徑。

來源

2009-08-10 Hamid

你有沒有嘗試過？如果是這樣，你可以編輯包含你的想法嗎？ – statenjason 2009-08-10 18:08:45

這是一個家庭作業問題嗎？ – 2009-08-10 18:13:05

@David，是的，聽起來像一個算法課程的項目。 – Steve 2009-08-10 18:30:00

這完全等同於具有所有負權重的最短路徑算法。要做到這一點，您需要確認沒有負重循環（在您的原始情況下，這可能相當於驗證沒有正負重循環）。最好的辦法是取權重的加法倒數並運行Bellman-Ford，然後取結果的加法倒數。

來源

2009-08-10 18:09:48

請參閱QuickGraph project，因爲它提供了實現圖的.NET數據結構，並且還提供了運算這些數據結構的算法。我確定你正在尋找的算法是在庫中實現的。

來源

2009-08-10 18:18:26

David Berger的答案是正確的，除非你的意思是一條簡單的路徑，每個頂點最多可以出現一次，在這種情況下，Bellman-Ford不會給出最長的路徑。既然你說權重是正的，當圖形有一個週期（從源頭可達）時，不可能存在最長的路徑，除非你的意思是簡單的路徑。最長的簡單路徑問題是NP完全的。見Wikipedia。

因此，我們假設您的意思是一個有向無環圖（DAG）。在線性時間內，假設你知道從u→v的每個u的最長路徑，可以計算從起始頂點到每個頂點v的最長路徑。這很簡單 - 您可以先對有向圖進行深度優先搜索，然後按照訪問它們的相反順序計算頂點的最長路徑。您也可以使用3色標記（打開但未完成的頂點爲灰色）檢測整個DFS的背部邊緣。請再次參閱Wikipedia瞭解更多信息。 DAG上的最長/最短路徑查找有時稱爲維特比算法（即使它假定了特定類型的DAG）。

我會首先嚐試線性時間動態規劃解決方案。如果你有循環，那麼貝爾曼 - 福特無論如何都不會解決你的問題。

來源

2009-08-10 19:28:52

如果不可達，最長的路徑可能存在循環。此外，如果有任何負重循環可達，Bellman-Ford可以返回負無窮大。因此，即使沒有明確地假設圖是非循環的，這仍然是一個合理的問題。也許這就是爲什麼你鏈接的第一篇維基百科文章推薦Bellman-Ford。 – 2009-08-10 20:26:51

當然，當你準備好你的拓撲順序時，DFS會檢測到來自源頭的子圖是否有一個循環。 – 2009-08-11 07:37:52

使用bellman-ford最長路徑的唯一原因是 1）有可達到的循環 2）但是所有這些循環都是0或負的權重（在權重反轉之前） – 2009-08-11 08:01:09

爲了萬一它幫助任何人，因爲我一直在尋找這一段時間，但找不到它，我用QuickGraph來解決一個問題，我不得不尋找最長的路徑，也符合一定的規則。這不是很優雅，因爲一旦我得到第一個結果，我就用蠻力對它進行了一些處理，但在這裏。

https://github.com/ndsrf/random/blob/master/LongestSkiPath/LongestSkiPath/SkiingResolver.cs#L129-L161

爲了獲得最長的路徑，你使用算法來找出最短用lenghts = -1。然後，爲了找到後續最長的路徑，我開始從最長路徑中刪除邊緣，以查看是否能夠根據問題的條件獲得「更好」最長路徑。

來源

2015-06-07 09:57:38 nadasurf

兩個頂點之間的最長路徑

回答

相關問題