使用時空折衷的最短路徑算法？

Question

問題：在未加權的無向圖中找到最短路徑。

廣度優先搜索可以找到兩個節點之間的最短路徑，但這可能會花費O（| V | + | E |）時間。預先計算的查找表將允許在O（1）時間內迴應請求，但是以O（| V |^2）空間爲代價。

我想知道：有它提供了一個時空權衡這更細粒度的算法？換句話說，是否有一個算法，其中：

1. 查找在超過O時間最短路徑（1），但比雙向廣度優先搜索
2. 更快使用預先計算的數據，其佔用小於空間O（| V |^2）？

在實際方面：圖爲800000個節點和被認爲是一個小型世界網絡。所有配對最短路徑表格的數量級都是千兆字節 - 這些日子並沒有離譜，但它不符合我們的要求。

但是，出於好奇，我在問我的問題。什麼讓我在晚上是不是「我怎樣才能減少所有對查找表的緩存未命中？」，但「有沒有我從來沒有聽說過的完全不同的算法？」

答案可能不是，沒關係。

Answer 1

您應該首先查找Dijkstra's algorithm找到最短路徑。 a *算法是一種變體，它使用啓發式算法來減少計算開始和目標節點之間的最佳路線（例如歐幾里得距離）所用的時間。您可以修改此啓發式以獲得性能或準確性。

Answer 2

看起來好像你的輸入集合必須非常大，如果一個查找表將會太大而無法存儲在磁盤上。我假設數據不適合RAM，這意味着無論您使用哪種算法都應該進行調整，以最大限度地減少讀取和寫入的數量。每當涉及磁盤空間==時間，因爲寫入磁盤是如此之慢。

你應該使用的確切算法取決於你有什麼樣的圖。 This research paper可能會對你感興趣。充分披露：我沒有自己讀過，但它似乎可能是你正在尋找的東西。

編輯：

如果圖形是（幾乎）相連接，其中小世界網絡是，查找表不能低於V^2小。這意味着所有查找都需要磁盤訪問。如果邊緣適合主內存，則每次只計算路徑可能會更快。否則，您可能會從包含所有最短路徑長度的表中計算路徑。您可以重建該表中的路徑。

關鍵是要確保表中在任一方向彼此靠近的條目在磁盤上也彼此靠近。這種存儲模式實現了：

1 2 1 2 5 6 
3 4 3 4 7 8 
     9 10 13 14 
     11 12 15 16 

它也適用於緩存層次結構。

爲了計算表格，您可以使用修改的Floyd-Warshall，您可以在其中處理塊中的數據。這可以讓你在合理的時間內執行計算，特別是如果你並行化它。