Dijkstra's Shortest Path

Dijkstra's algorithm finds the shortest path from one source to every other vertex in a graph whose edges have weights — think road distances, network latencies, or costs. It is the workhorse behind GPS routing and is one of the most-asked graph algorithms in interviews.

Intuition

Imagine a wildfire starting at vertex A. Fire spreads along edges, and a longer or higher-weight edge just takes more time to burn across. The first moment the fire reaches a vertex is its shortest distance from A — there is no faster way for the fire to have gotten there.

Dijkstra is exactly this "fire" simulation, sped up. Instead of advancing time continuously, we jump straight to the next vertex the fire reaches: the nearest vertex we have not burned yet. We "burn" (finalize) it, then check whether reaching it opens up a cheaper route to any of its neighbors. A min-priority-queue hands us that nearest vertex in O(log n) each time — that is the engine that makes the greedy choice fast.

Walk through it

On the right, every vertex carries a tentative distance label: A starts at 0, everyone else at ∞ ("not reached yet"). Each round, we pop the nearest unfinalized vertex (it turns blue), then look at each of its edges.

Relaxing edge u → v asks one question: is dist[u] + weight smaller than dist[v]? If yes, we just found a cheaper way to reach v, so we lower its label. Watch the distances ratchet down: when we pop C (distance 1), it relaxes B from 4 down to 3 (the path A→C→B costs 1 + 2 = 3, beating the direct A→B edge of 4). After a vertex's distance can no longer improve, it turns green and is finalized forever. When every vertex is green, the labels are the final shortest distances: A=0, B=3, C=1, D=4, E=7.

The code, line by line

import heapq
 
def dijkstra(graph, src):
    dist = {v: float("inf") for v in graph}
    dist[src] = 0
    pq = [(0, src)]            # (distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue          # stale entry — skip
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

• dist holds the best distance found so far to each vertex; everyone but the source starts at infinity.
• pq is a min-heap of (distance, vertex) pairs. heappop always returns the smallest distance first — that is the greedy "pick the nearest unfinalized vertex" step.
• The if d > dist[u]: continue guard skips stale entries. We never delete from a heap, so a vertex can sit in pq more than once; if we already found a shorter path to u, this older, larger entry is ignored.
• Lines 12–14 are the relaxation: if going through u gives v a smaller distance, update dist[v] and push the new, better entry onto the heap.

Complexity

Every edge can trigger at most one heappush, and every push/pop is O(log V), giving O((V + E) log V). The space is O(V + E) for the graph plus the distance map and the heap.

When to use / pitfalls

Practice