Dijkstra算法的运行时分析，得到O(Vlog(V) + VE)

Question

我试图使用最小优先级队列(使用Fibonacci堆实现)来确定dijkstra算法的运行时间。

密码

​

分析:我知道对于Fibonacci堆插入是减少/插入键是O(1)，而提取min是O(log(n))

第1至第3行:对于每个顶点，运行时为O(V)

第4行中的循环采用O(V)，但是ExtractMin对于每个边也采用O(log(V))，也就是第6-7行的for循环(它的O(E) )。

因为for循环在while循环中，所以我有V(log(V) + E)

所以我得到O(V + V_log(V) + V_E)，可以归结为O( V_log(V) + V_E)。

但是大多数文章都指出它是O( V*log(V) + E)，是因为E>V还是我做错了什么？

Answer 1

每个顶点最多会被ExtractMin拔出一次，这样内部for循环(在while循环的所有迭代中)最多会选择每个边；因此E，而不是V*E，项。