Prove Dijkstra's O(E + VlogV) complexity

[SadPaul]

Homework Statement

Prove that Dijkstra's time complexity O(E + VlogV) with Fibonacci priority queue is the best by reducing it to a sorting problem

Relevant Equations

-

My effort:
I think that the sorting problem in question is Heap Sort which has an O(logV) complexity, but how can I operate with that information so I can solve this? Can you help me by giving me the outline of an idea?

 

[fresh_42]

I would reason this way:

You have to visit each edge and each vertex at least once, for otherwise you might lose the minimum. This gets you $O(|E|\cdot T_1 +|V|\cdot T_2)$ where $T_i$ is the time you use at each edge: $T_1=T(\text{decrease key})$ and the time at each vertex: $T_2=T(\text{extract minimum})$.

To extract minimum we use Fibonacci Heaps which run in $O(\log n)$. So all you have to do is to show that $T_1=O(1)$ and $T_2 > O(\log |V|)$. So you have to show the lower boundary for the sort operation via Fibonacci heap (sufficiency) and that any sort algorithm needs at least $O(\log n)$ (necessity).