为什么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）。 –

回答