问题：在未加权的无向图中找到最短路径。
广度优先搜索可以找到两个节点之间的最短路径，但这可能需要 O(|V| + |E|) 时间。预先计算的查找表将允许在 O(1) 时间内回答请求，但以 O(|V|^2) 空间为代价。
我想知道的是：是否有一种算法可以提供更细粒度的时空权衡？换句话说，是否有一种算法：
在实际方面：该图有 800,000 个节点，被认为是一个小世界网络。全对最短路径表的数量级为千兆字节——这在当今并不令人发指，但它不符合我们的要求。
但是，我是出于好奇而问我的问题。让我夜不能寐的不是“我如何才能减少所有对查找表的缓存未命中？”，而是“是否有一种我从未听说过的完全不同的算法？”
答案可能是否定的，这没关系。