Dijkstra的算法 - 複雜度

我有一個理解Djisktra算法的複雜性的問題，並希望有人能糾正我。Dijkstra的算法 - 複雜度

對於我的例子，我拍了一個有n個頂點的完整圖。

您選擇一個起始頂點，讓我們說a1，標記它，然後計算邊上的所有n-1權重。 O（n）

你挑最小的一個。假設頂點a2並標記它。 O（n）

之後，您將計算邊上的n-2個新權重並查找下一個未標記的頂點以添加標記的頂點集。

依此類推...

該算法運行直到您可以標記所有頂點。複雜性：n-1 + n-2 + ... + n - （n-1）=在O（n^2）中的Binom（n，2），而不是O（n * ln（n））想。

我讀過很多次人們使用堆進行優化，但是我仍然沒有看到如何避免Binom（n，2）的計算。

我必須在某些時候是錯的，但看不到在哪裏。

2016-03-23 Imago

什麼是n，爲什麼你必須在每個頂點做n次？ –

如果你有一個完整的圖表，那麼當然你不能做比O（n^2）更好的選擇 - 因爲這就是你輸入的大小。

如果您沒有完整的圖表，並且將邊緣存儲在鄰接列表中，那麼您可以做得更好。您仍然需要查看所有邊，但是使用優先級隊列可以管理O（e + n log n），其中e是鄰接列表中的邊數。

2016-03-23 18:22:07 comingstorm

好的。這讓我非常沮喪，因爲在所有的文獻中，我只讀到了你說的O（E + n + log n），這讓我很困惑。我必須檢查如何使用優先級隊列。謝謝您的回答。 – Imago

完成與否，你仍然得到O（e + n log n）。只是當圖完成時，e = n^2，給出O（n^2 + n log n）= O（n^2）。 –

回答