使用时空折衷的最短路径算法？

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，您可以在其中处理块中的数据。这可以让你在合理的时间内执行计算，特别是如果你并行化它。