Bi Directional Dijkstra

雙向Dijkstra

問題

給定具有非負邊權重的圖形，一個源頂點s和目標vertec t 。找到S和T之間的最短路徑

但是，為什麼我們不只是使用Dijkstra的算法來解決問題呢？

0（E + VLOGV）是Dijkstra算法最糟糕的時間複雜性，該算法非常快。但是，對於具有2000萬個頂點和5000萬個邊緣的圖表，它平均可以工作幾秒鐘。因此，我們需要更快的東西。

在進行雙向搜索的細節之前，讓我們探索“六個分離程度”的概念

• 1929年，匈牙利作家Frigyes Karinthy首次在他的短篇小說鏈中提出了“六度分離”的概念。
• 六個分離的想法是，世界上所有的生物和其他所有事物都彼此六分之六或更少。

現在，讓我們查看最受歡迎的社交網絡Facebook。假設Facebook上的一個普通人大約有100個朋友。然後，如果我們考慮那個人的朋友的朋友，那就是100*100，即10,000個朋友的朋友。如果我們考慮“朋友的朋友的朋友” ，那將是100萬倍或100萬倍。如果我們繼續六次，我們將有1盧比的人。

但是，全球人口為76億。

現在，我們如何通過社交網絡上的連接找到兩個隨機的人A和B之間的最短路徑？

讓我們考慮雙向搜索。因此，我們將考慮B的朋友的朋友和B的朋友的朋友。

請注意，我們將有大約100萬個朋友的朋友的朋友和B的朋友朋友。因此，在這種情況下，我們總共只考慮200萬人。

普通的Dijkstra的算法必須在社交網絡上看大約2億人，以找到A和B之間的最短路徑。

什麼是雙向搜索

在此，我們同時進行了兩個同時搜索：一個從初始狀態前進，一個從目標向後進行，當兩者在中間相遇時停止。

圖G上的雙向dijkstra的偽代碼g

• 構建GR（反向圖）
• 從G中的S（源）和GR中的T（target）啟動Dijkstra
• 在G和GR中的Dijkstra步驟之間的交替
• 當在G和GR中處理某個頂點“ V”時停止。
• 計算S和T之間的最短路徑。

S和T之間的最短路徑的計算是從G中的S向前dijkstra中的距離估計值。讓Dister [u]是gr中T的向後dijkstra中的距離估計值。在G和GR中處理了一些節點“ V”之後，從S到T的最短路徑通過了一些節點“ U”，該節點在G，GR或GR中進行處理， D（S，T）= Dist [U] + ISTR [U]