圖中不應該是邊的邊的頂點之間的最短路徑

我需要找到加權無向圖中每條邊的最短替代路徑，即假設我有一個egde（a，b）in一個圖表，那麼我想計算在直接路徑跳過的候選點a和b之間的最短路徑，即邊（a，b）。如果沒有替代路徑，那麼距離應該是無限的。我會爲圖的每個邊做這個。我試着用dijkstras算法（當遇到目標頂點時會破壞），但是需要太多時間來爲每個邊單獨計算路徑，特別是在沒有其他選擇的情況下路徑是可能的（在這種情況下，必須遍歷整個圖）。你能否提出其他解決方案？圖中不應該是邊的邊的頂點之間的最短路徑

來源

2012-08-09 Nikhil Garg

你爲什麼不直接刪除圖中的「不允許」邊緣，然後運行Dijkstra或任何其他「正常」路徑查找算法？ – Nobody 2012-08-09 17:08:55

如果Dijkstras花費太多時間，那麼我認爲你運氣不好。不要認爲現在有更好的算法。 – Egor 2012-08-09 17:11:42

當您找到要升級的下一個節點時，您的dijkstra實現是否使用最小堆？或者你只是遍歷所有的版本？ – titus 2012-08-09 17:19:46

-1

Here是我前段時間寫的dijkstra實現，它使用stl make_heap更有效地找到下一個節點。實施很可能是正確的。
編輯：在該示例中文件從讀取時，n是頂點的數目，m是邊數，a和b是邊緣的頂點，其方向是從a到b，c是重量。
由於Nobody提到，您應該刪除邊緣，然後將其添加回來，以保持算法原樣。

來源

2012-08-09 17:27:25 titus

我想我會做的是適應Dijkstra的算法，以便我最初填充堆長度/優先隊列長度爲2的所有路徑不使用該邊緣（感謝titus捕捉我以前的錯誤）。這樣，您得到的結果將排除只包含一個邊的路徑。結果會爲您獲取一切特定來源的所有信息，您可以在所有可能的來源中重複此操作。

來源

2012-08-09 17:40:11

我想你可能最終得到的結果是a-> c-> b，其中a-> c實際上是a-> b-> c。沒有？在添加所有長度爲2的路徑時，仍然需要注意不要使用a-> b。2 – titus 2012-08-09 17:48:25

啊，真的。（我最初實際上是誤讀了這個問題，但是我認爲如果我們只是做了這個檢查就沒問題） – 2012-08-09 17:55:14

-1

Dennis Meng建議的解決方案是我想的。但是有一些優化（預處理）可以使你的實現更快。

將連接組件（樹）集中的圖分隔[提示：使用DFS查找連接的組件]。 - 通過這種方式，如果在tree節點u中找不到對（u，v）對的最短路徑，那麼您可以跳出（內部）循環。
維護每個節點與其對應的樹之間的映射。 - 這將在實現幫助第1步

來源

2012-08-09 21:43:46

-1

你只需要在其上進行dijkstras之前，只需刪除從圖形目標邊緣.....

來源

2012-12-26 04:39:58

圖中不應該是邊的邊的頂點之間的最短路徑

回答

相關問題