爲什麼Dijkstra最糟糕的情況是E + VlogV？

-3

請解釋爲什麼你認爲這個算法應該是E（logV）。 –

對不起，迪傑斯特拉犯了一個錯字。 – Mehrdad

常見的實現*是* O（| E | log | V |）。您需要一個支持恆定時間減少鍵操作的優先級隊列來獲得更好的漸近界。你的鏈接指出了這一點。 – tmyklebu

在最壞的情況下E > V所以複雜性是E + VlogV它可以與E+ElogV替換爲複雜ElogV是什麼意思？

2013-06-04 03:15:15 Mzf

的Dijkstra's algorithm最壞情況下的時間複雜度依賴於它是如何實現的：

Simple Implementation：O((E * c1) + (V * V)) = O(E + V^2) ~ O(V^2)

Using Fibonacci Heap：O((E * c2) + (V * log V)) = O(E + V log V) ~ O(V log V)

2013-06-04 04:56:12

對於堆解決方案的分析 - 如果是E = V^2的稠密圖，這是不準確的。在這種情況下，最壞的情況仍然是O（E）= O（V^2）。 –

回答