增量Dijkstra或最短路徑算法？

Question

我有一個初始有向圖G，從中我不時刪除邊（不添加新的邊）。我不刪除節點（儘管有些可能會斷開連接）。 有沒有辦法有效地重新計算最短路徑而無需再次從頭開始運行Dijkstra？初始節點永遠不會改變。

如果沒有Dijkstra算法的增量版本，其他一些算法會很好。但我不能使用A *（我記得它有一個增量版本），因爲我沒有任何啓發來知道我離目的地有多遠。

謝謝

Answer 1

您可以跟蹤使用的邊緣。如果刪除一個，則可以使用它們查找需要更新的所有節點。

其餘節點不需要更新。如果刪除邊緣，只能使路徑更長。

貫穿所有邊緣，並且如果源不需要更新，但目標確實將目標添加到Dijkstra優先級隊列。 一旦你完成了運行常規Dijkstra算法來計算新的成本。

這就是說你可能仍然運行整個dijkstra，如果你從源頭中刪除一個鏈接。因此，如果您不嘗試刪除已使用的鏈接（因爲很可能無法刪除已刪除的鏈接），或者刪除鏈接以使其距離源代碼很遠（這樣您只需要更新幾個節點）。