我們如何知道Dijkstra算法是最好的單源最短路徑算法？

Question

我知道Dijkstra的算法是如何工作的，它可以在時間O（m + n log n）時間內運行。我們如何知道單源最短路徑沒有比這更好的算法？

Answer 1

Dijkstra算法實際上並不一定是計算圖中單源最短路徑的最快算法。例如，如果您知道所有邊都具有整數權重，並且假定機器字足夠大以容納任何整數，則可以使用由Thorup開發的在時間O（m + n）中運行的算法，其中比Dijkstra算法漸近地快。如果邊緣未加權，或者如果它們都具有相同的權重，那麼一個簡單的BFS在時間O（m + n）中執行此操作。