使用空间-时间权衡的最短路径算法？

Question

问题：在一个无权、无向的图中寻找最短路径。

广度优先搜索可以找到两个节点之间的最短路径，但是这可能需要O（|V| + |E|）的时间。预计算查找表可以在O（1）的时间内回答请求，但代价是O（|V| ^ 2）的空间。

我想知道的是：是否有一种算法提供了更细粒度的时空权衡？换句话说，是否有一种算法：

1.在比双向广度优先搜索更快的时间内找到最短路径； 2.使用的预计算数据占用的空间小于O（|V| ^ 2）？

在实践中，该图有800,000个节点，被认为是一个小世界网络。全对最短路径表将达到几千兆字节的数量级 - 这在今天不算过分，但它不能满足我们的要求。

然而，我问这个问题只是出于好奇。让我失眠的不是“如何减少全对查找表的缓存未命中？”，而是“是否有完全不同的算法存在，而我从未听说过？”答案可能是否定的，那也没关系。

- Chris Mounce

---

这个图大概会有多少个节点？ - danben

图形是密集还是稀疏？有多少个节点？有多少条边？ - Jørgen Fogh

Answer 1

你应该先看一下迪杰斯特拉算法来寻找最短路径。A*算法是一种变体，它使用启发式方法来减少计算起点和终点之间最优路径所需的时间（例如欧几里得距离）。你可以修改这个启发式方法以提高性能或准确性。

- James Westgate

Answer 2

如果查找表太大无法存储在磁盘上，那么你的输入集合似乎必须非常庞大。我假设数据不会适应内存，这意味着你使用的算法应该经过调优，以最小化读写操作的次数。每当涉及到磁盘时，空间等于时间，因为写入磁盘的速度非常慢。

你应该根据所拥有的图形类型选择合适的算法。这篇研究论文可能对你有兴趣。完全透明地说，我自己没有阅读过，但它似乎符合你的需求。

编辑：

如果图形（几乎）是连通的，就像一个小世界网络一样，查找表的大小不能小于V^2。这意味着所有的查找都需要访问磁盘。如果边可以适应主内存，每次只计算路径可能更快。否则，你可以通过计算包含所有最短路径长度的表来计算路径。你可以从该表中重构路径。

关键是要确保在磁盘上相互靠近的条目在任何方向上也相互靠近。以下存储模式可以实现这一点：

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

它也可以很好地与缓存层次结构配合使用。

为了计算表格，您可以使用修改过的Floyd-Warshall算法，在块中处理数据。这将使您能够在合理的时间内执行计算，特别是如果您并行化它。

- Jørgen Fogh

---

这些内容都非常有用，关于构建完整查找表的最有效方法，但那不是我的问题 - 如果我没有表达清楚，对不起。我的意思是问，是否存在一种算法，它需要超过O（1）的时间来查找两个任意节点之间的最短路径，并使用占用少于（| V |）（| V | -1）空间的预计算数据？答案可能是否定的，那也没关系 - 一个实际的问题引起了我对这个主题的兴趣，但现在我只是想满足自己的好奇心。 - Chris Mounce