缺少給定邊的最短路徑

Question

假設給出加權圖G（V，E）。

該圖包含Ñ頂點（編號從0到N-1）和中號邊緣雙向。

每個邊緣（六，VJ）具有陽性距離d（即，在兩個頂點vivj之間的距離是d）

有任意兩個頂點之間atmost一個邊緣，並且還存在沒有自我循環（ie.no邊緣頂點連接到 本身。）

此外，我們給出小號源頂點和d目標頂點。

let Q是查詢的數量，每個查詢包含一個邊沿e（x，y）。假設邊緣（x，y）在原始圖中不存在，我們必須找到從源S到目的地D的最短路徑。 如果沒有從S到d存在任何路徑，則我們有打印號

約束是高0 < =（N，Q，M）< = 25000

如何解決這個問題有效？

直到現在我所做的是實現了簡單的Dijakstra算法。

對於每個查詢Q，每次我很分配（X，Y），以無限 和發現Dijakstra最短路徑。

但這種方法會很緩慢，因爲整體的複雜性將是Q（時間Dijastra Shortes路徑的複雜性）*

例::

N=6,M=9 
S=0 ,D=5 

(u,v,cost(u,v)) 
0 2 4 
3 5 8 
3 4 1 
2 3 1 
0 1 1 
4 5 1 
2 4 5 
1 2 1 
1 3 3 

Total Queries =6 

Query edge=(0,1) Answer=7 
Query edge=(0,2) Answer=5 
Query edge=(1,3) Answer=5 
Query edge=(2,3) Answer=6 
Query edge=(4,5) Answer=11 
Query edge=(3,4) Answer=8 

Answer 1

首先，計算從源節點到目的地的最短路徑樹。其次，遍歷所有查詢並在查詢指定的邊上剪切最短路徑;這定義了一個min-cut問題，在這個問題中，源節點和一個分區的邊界之間的距離以及另一個分區的邊界和目的地的邊界;你可以很容易地計算這個問題，最多O(|E|)。

因此，該算法需要O(Q|E| + |V|log|V|)，當|V|log|V| > |E|時漸近地快於初始解。

該解決方案重用了Dijkstra的計算，但仍然單獨處理每個查詢，因此可能還有空間通過觀察由邊緣引起的切割的形狀來利用在先前查詢中在連續查詢中所做的工作。

Answer 2

一個簡單的優化：第一上運行的Dijkstra完整的圖形（沒有刪除邊緣）。

然後，對於每個查詢 - 檢查請求的邊是否屬於該最短路徑。如果沒有 - 刪除這個邊緣不會有任何區別。

Answer 3

對於每個查詢，圖只會非常輕微地改變，因此您可以重複使用很多計算。

我建議以下方法：

1. 計算從小號到所有其他節點的最短路徑（Dijkstras算法併爲你的話）。這會給你一個最短路徑樹T。
2. 對於每個查詢，取這棵樹，用查詢中的邊（x，y）修剪。這可能是原始樹（如果（x，y）不在樹上的任何位置）或更小的樹T'。
   • 如果d在T「，你可以把原來的最短路徑
   • 否則啓動Dijkstra算法，而是使用你已經從T的標籤」（這些路徑已經是最小的）作爲永久性標籤。

如果您在步驟2中運行Dijkstra算法可以重複使用下面的方式修剪的牛逼樹的一部分：要標記一個節點的永久（這是一個節點每次不在T'），您可以將此節點的整個子樹（從原始樹T）附加到新的最短路徑樹並將其所有節點標記爲永久。

這樣，您可以從第一個最短路徑運行中重新使用盡可能多的信息。

---

在您的例子，這將意味着：

計算最短路徑樹： 0-> 1-> 2-> 3-> 4-> 5 （在這種情況下很簡單的）

現在假設我們得到查詢（1,2）。

我們修剪邊緣（1,2）留給我們 0-> 1

從那裏，我們開始的Dijkstra得到2個3下一個永久標記節點。 我們連接1至2和1至3個新的最短路徑樹，並附上3老樹： -0-> 1-> 3-> 4-> 5

因此，我們得到的最短只需運行一個額外的Dijkstras算法步驟。

---

算法的正確性從所有路徑遵循在樹Ť至多爲只要在從查詢（其中每個最短路徑只能更長）的新圖形。因此，我們可以重用仍然可行的樹中的每條路徑（即沒有刪除邊的地方）。

如果性能很重要，可以通過大量的實施技巧來提高Dijkstra的性能。一個好的入口點可能是DIMACS Shortest Path Implementation Challenge。