What is the time complexity of Dijkstra's with a Binary Heap?

What is the time complexity of Dijkstra's with a Binary Heap?

Approach: Analyze the cost of V extract-min and E decrease-key operations.

O((V + E) log V). Each vertex is extracted once (V log V) and each edge might cause a decrease-key operation (E log V).

Follow-up: How does using a Fibonacci Heap change the complexity?

Key concepts: O((V+E) log V), binary heap, priority queue.