问题:在未加权，无向图中找到最短路径。
广度优先搜索可以找到两个节点之间的最短路径，但这可能需要O(| V | + | E |)时间。预先计算的查找表将允许在O(1)时间内答复请求，但以O(| V | ^ 2)空间为代价。
我想知道的是:是否存在提供更精细的时空折衷的算法？换句话说，有没有一种算法可以:
在实践方面:该图有800,000个节点，被认为是小型世界网络。全对最短路径表的数量级为千兆字节-如今并不算太贵，但它不符合我们的要求。
但是，出于好奇我在问我的问题。是什么让我彻夜难眠，是而不是“如何减少全对查询表的高速缓存未命中率？”，但是“那里有一种我从未听说过的完全不同的算法吗？”
答案可能是否定的，那没关系。
最佳答案
您应该首先从Dijkstra's algorithm查找最短路径。 a *算法是一种变体，它使用启发式方法来减少计算起始节点与目标节点之间的最佳路线(例如欧几里得距离)所花费的时间。您可以修改此试探法以提高性能或准确性。
关于algorithm - 使用时空权衡的最短路径算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2724937/