動態更新最短路徑

Question

我有一個圖表，我經常需要知道所有最短路徑（或更確切地說它們的長度）。因爲我不想重新計算它們，所以我將它們存儲在一個簡單的數組中，然後從那裏檢索它們。然而，由於圖形也可能隨着時間而改變，我將不得不在給定時間重新計算它們。

對於現在的以下變化可能會發生：

• 添加節點和邊緣給它的圖形

• 改變一個邊緣

• 的長度增加一個新的邊緣的圖

• 刪除邊或刪除節點

在所有情況下，所有節點將始終連接並且所有邊都具有正權重。該圖也是無向的。操作的順序是這樣的，所有節點將始終來自圖的相同組件。如果在添加節點或邊之前已經添加了其他節點和邊，以便圖永遠不會分離。

現在我打算只做更新，然後通過圖結構傳播所有更改。但是我不確定如何正確處理這個問題。你將如何嘗試實現這些緩存長度的更新。

編輯：

你們當中有些人已經指出，當一個節點被添加或鏈接改變可能是neccessary重新計算的一切。例如，當所有距離通過更新而改變時，這可能是例如。但是，如果我只是通過圖形傳播更改並執行類似於完成dijkstras的方式，我可能必須多次放鬆同一個節點，因爲我可能不會選擇最佳順序。問題是如何訂購放鬆步驟，所以我儘可能避免多次更新。

如果沒有我想到的實際想法，這是沒有多大意義的，但我希望這可以澄清更多。

Answer 1

D* family of search algorithms與更新動態變化圖表中的短路徑一模一樣。該算法是爲移動機器人路徑規劃問題開發的。雖然算法只返回從目標到當前機器人位置的最短路徑，但您也可以使用它們的簿記和更新規則來處理所有最短路徑問題。

Answer 2

您可以輕鬆處理刪除邊緣/節點的情況。只需跟蹤節點之間的實際路徑。然後，當邊/節點被刪除時，通過你的路徑，看看哪些受到改變的影響。重新計算這些的最短路徑。

在增加邊重量的情況下，可以使用相同的技術。

其他案例明顯更難以處理。我不知道會加快重新計算的算法/數據結構。