Dijkstra's algorithm: time and space complexity

High interview relevanceRoadmap: Advanced

Time	O((V + E) log V) with a binary heap
Space	O(V + E)

Why it costs this much

Each edge can push at most one entry onto the heap, and each push or pop costs O(log V), so the edges dominate at O(E log V).

Code

import heapq
def dijkstra(graph, src):                  # graph[u] = [(v, weight), ...]
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)         # O(log V) per pop
        if d > dist.get(u, float("inf")):
            continue                       # stale entry
        for v, w in graph[u]:              # each edge relaxed at most once
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))   # at most E pushes in total
    return dist

Common pitfalls

It gives wrong answers with negative edge weights; use Bellman–Ford instead. Skip stale heap entries when you pop them.

Operation by operation

Operation	Best	Average	Worst	Space
Dijkstra shortest path	O((V + E) log V)	O((V + E) log V)	O((V + E) log V)	O(V + E) with lazy deletion; O(V) with decrease-key

Dijkstra shortest path. Binary heap and an adjacency list. Non-negative edge weights only. Negative weights give wrong answers. With a Fibonacci heap it is O(E + V log V).