Let G(V, E) an undirected graph with positive edge weights. Dijkstra's…

Key idea: count the number of priority-queue operations and multiply by their cost with a binary heap.

• Extract-min: performed once for each vertex (|V|), each extract-min on a binary heap costs O(log |V|), giving O(|V| log |V|).

• Decrease-key (priority updates during edge relaxations): can occur up to once per edge in the worst case (|E|), each costing O(log |V|) on a binary heap, giving O(|E| log |V|).

Total running time: O((|E| + |V|) log |V|).

Notes:

• Using a Fibonacci heap reduces decrease-key to amortized O(1), yielding O(|E| + |V| log |V|).

• Using a simple array or adjacency-matrix selection gives O(|V|^2), which can be better for very dense graphs but is not the binary-heap bound.

• If the graph is sparse with |E| = O(|V|), the bound simplifies to O(|V| log |V|).