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(logV)O(\log V). Total time: O(ElogV)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(VlogV+E)O(V \log V + E), but binary heap is simpler and fast enough for competitive programming.