Graph Theory37 sections · 1633 units
Open in Course

Complexity of Dijkstra

Time and space analysis

You process every edge once. For every edge, you might push to the priority queue. Pushing takes O(log⁡V)O(\log V). Total time: O(Elog⁡V)O(E \log V) with a binary heap. Space: O(V+E)O(V + E) for adjacency list and distance array, plus O(V)O(V) for the priority queue.

With Fibonacci heap, you can get O(Vlog⁡V+E)O(V \log V + E), but binary heap is simpler and fast enough for competitive programming.