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

Question

问题：在未加权的无向图中找到最短路径。

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

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

在实际方面：该图有 800,000 个节点，被认为是一个小世界网络。全对最短路径表的数量级为千兆字节——这在当今并不令人发指，但它不符合我们的要求。

但是，我是出于好奇而问我的问题。让我夜不能寐的不是“我如何才能减少所有对查找表的缓存未命中？”，而是“是否有一种我从未听说过的完全不同的算法？”

答案可能是否定的，这没关系。

Answer 1

您应该首先查看Dijkstra 算法来查找最短路径。a*算法是一种变体，它使用启发式方法来减少计算起始节点和目标节点之间的最佳路线（例如欧几里德距离）所需的时间。您可以修改此启发式以提高性能或准确性。