Recall that Dijkstra’s algorithm greedily selects the next closest vertex using a priority queue; explain why a binary heap gives the stated O((E + V) log V) bound.

Derive the exact number of heap operations (insert, decrease-key) across all iterations and show how their logarithmic factors combine to yield the overall complexity.

Prove that any comparison-based priority queue must perform Ω(log V) work per edge relaxation in the worst case, thereby establishing the heap’s asymptotic optimality for Dijkstra’s algorithm.