以单源最短路径举例。大部分人平常使用的都是普通 dijkstra 或者 堆优化的 dijkstra 或者 spfa。相信不少人都知道可以使用斐波那契堆将 dijkstra 优化成 O(nlogn+m)O(n \log n+m)O(nlogn+m)。然后今年(也有可能是去年),有国外学者宣布研究出了大常数的单源最短路径算法,复杂度为 O(nloglogn+m)O(n \log \log n + m)O(nloglogn+m) 的算法。而单源最短路径算法的理论最优解下限明显是 O(n+m)O(n+m)O(n+m),那请问,在我们找到(也有可能找不到) O(n+m)O(n+m)O(n+m) 的算法之前,我们能否证明或者证伪存在 O(n+m)O(n+m)O(n+m) 的算法.