NetworkX的「Bidirectional Dijkstra」

Question

我剛剛閱讀了使用雙向搜索的最短路徑Dijkstra算法的NetworkX實現（位於this）。這種方法的終止點是什麼？

Answer 1

我將基於networkx的實現。

雙向Dijkstra在兩個方向上遇到相同節點時停止 - 但它在該點返回的路徑可能不通過該節點。它正在進行額外的計算以追蹤最短路徑的最佳候選者。

我要立足於您的評論我的解釋（上this answer）

考慮一個簡單的圖形（與節點A，B，C，d，E）。該圖的邊緣及其權重爲：「A-> B：1」，「A-> C：6」，「A-> D：4」，「A-> E：10」，「D-> C：3" ， 「C-> E：1」。當我在這個圖的兩邊使用Dijkstra算法時：在前面它找到B在A之後，然後D在後面找到C在E之後，然後D.在這一點上，兩個集合具有相同的頂點和交點。這是終止點還是必須繼續？因爲這個答案（A-> D-> C-> E）不正確。

僅供參考，這裏的圖：

當我運行在反的（非定向）網絡上networkx的雙向Dijkstra算法，你聲稱評論："A->B:1","A->C:6","A->D:4","A->E:10","D->C:3","C->E:1"：它給了我：(7, ['A', 'C', 'E'])，不A-D-C-E。

問題是在誤解它在做什麼之前它停止。它在搜索節點方面完全符合你的期望，但是當它這樣做時，會發生額外的處理以找到最短路徑。當它從兩個方向到達D時，它已經收集了一些可能更短的其他「候選」路徑。不能保證僅僅是因爲從兩個方向到達節點D，最終成爲最短路徑的一部分。相反，在從兩個方向到達節點的點上，當前候選最短路徑比它繼續運行時將找到的任何候選路徑更短。

該算法有兩個空簇開始，每個A或E

{}   {} 

相關聯，它會建立「集羣」圍繞每個。它首先把A與A

{A:0}   {} 

相關的集羣現在，它會檢查是否A已經在集羣E在（目前爲空）。不是這樣。接下來，它查看每個鄰居A並檢查它們是否在E附近的集羣中。他們不是。然後它將所有這些鄰居放入一個堆（如有序列表）中，即A即將到來的鄰居A的路徑長度。稱此爲的A

clusters     .....  fringes 

{A:0}   {}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[] 

現在檢查E '邊緣'。對於E它做對稱的事情。將E放置到其集羣中。檢查E不在A附近的羣集中。然後檢查它的所有鄰居，看看是否有任何在A附近的羣集（他們不是）。然後創建E的邊緣。

clusters         fringes 
{A:0}   {E:0}  .....  A:[(B,1), (D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

現在它回到A。從列表中取出B，並將其添加到集羣A左右。它檢查B的任何鄰居是否在圍繞E的簇中（沒有鄰居要考慮）。因此，我們有：

clusters         fringes 
{A:0, B:1}  {E:0}  .....  A:[(D,4), (C,6), (E,10)] 
             E:[(C,1), (A,10)] 

返回E：我們添加C托特他集羣E和檢查C任何鄰居是否是A在羣集中。你知道什麼，有A。所以我們有一個候選人最短路徑A-C-E，距離爲7.我們將繼續這樣做。我們增加D添加到邊緣E（距離4，因爲它是1 + 3）。我們有：

clusters         fringes 
{A:0, B:1}  {E:0, C:1}  ..... A:[(D,4), (C,6), (E,10)] 
             E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

返回A：我們從它的邊緣，D獲得接下來的事情。我們將其添加到集羣約A，並注意其鄰居C是在集羣約E。所以我們有一個新的候選路徑，A-D-C-E，但它的長度大於7，所以我們放棄它。

clusters         fringes 
{A:0, B:1, D:4}  {E:0, C:1}  ..... A:[(C,6), (E,10)] 
              E:[(D,4), (A,10)] 

candidate path: A-C-E, length 7 

現在我們回到E。我們看看D。它位於A附近的羣集中。我們可以肯定的是，我們將遇到的任何未來候選人路徑的長度至少與我們剛剛查明的A-D-C-E路徑一樣大（這種說法不一定很明顯，但它是這種方法的關鍵）。所以我們可以停止。我們返回前面找到的候選路徑。