我们如何知道Dijkstra算法是最好的单源最短路径算法？

Question

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

Answer 1

Dijkstra算法实际上并不一定是计算图中单源最短路径的最快算法。例如，如果您知道所有边都具有整数权重，并且假定机器字足够大以容纳任何整数，则可以使用由Thorup开发的在时间O（m + n）中运行的算法，其中比Dijkstra算法渐近地快。如果边缘未加权，或者如果它们都具有相同的权重，那么一个简单的BFS在时间O（m + n）中执行此操作。