algorithm - 我们怎么知道 Dijkstra 算法是最好的单源最短路径算法？

Question

我知道 Dijkstra 的算法是如何工作的，并且它可以在 O(m + n log n) 时间内运行。我们怎么知道没有比这更好的单源最短路径算法了？

Answer 1

Dijkstra 算法实际上不一定是计算图中单源最短路径的最快算法。例如，如果你知道所有的边都有整数权重并假设一个机器字大到足以容纳任何这些整数，那么你可以使用由 Thorup 开发的算法，该算法运行时间为 O(m + n)，它比 Dijkstra 算法渐近地快。如果边没有加权，或者它们都具有相同的权重，那么简单的 BFS 会在 O(m + n) 时间内完成。