Dijkstra's shortest path

Dijkstra's algorithm finds the shortest path from one source to every other node when edge weights are nonnegative. It is breadth-first search generalized to weights: instead of a plain queue it uses a priority queue keyed by the best distance found so far, and it greedily finalizes the closest unsettled node at each step.

Why nonnegative weights

The correctness rests on a greedy claim: when a node is popped with the smallest tentative distance, that distance is final. This holds only because every edge is nonnegative, so any alternative route, which would have to leave through some not-yet-finalized node that is already at least as far, can never come back cheaper. A single negative edge breaks that argument, which is why graphs with negative weights need Bellman-Ford instead.

Relaxation and the invariant

Each node carries a tentative distance, initially infinity except the source at zero. Relaxing an edge $(u,v)$ checks whether going through $u$ beats $v$'s current distance and, if so, lowers it. Popped nodes are settled and never revisited. This lazy variant pushes a fresh entry on every improvement and simply skips stale entries when popped (a distance larger than the one already recorded), which avoids needing a decrease-key operation.

A* and the rest of the family

Adding an admissible heuristic $h(n)$ that never overestimates the remaining distance turns the priority key into $g(n)+h(n)$ and gives A*, which explores far fewer nodes toward a single target (Hart et al. 1968). With zero weights Dijkstra degenerates to BFS; with negative weights use Bellman-Ford; for all-pairs shortest paths use Floyd-Warshall.

Step by step

1. Set the source distance to 0 and push it on a min-heap.
2. Pop the node with the smallest tentative distance.
3. Skip it if its popped distance is stale (already improved).
4. Relax each outgoing edge and push any improved neighbor.
5. Repeat until the heap is empty.

import heapq

def dijkstra(graph, start):
    # graph: {u: [(neighbor, weight), ...]}
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue                      # stale entry, already improved
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Complexity (time and space)

With a binary heap, $O((V + E)\log V)$: each edge can push one heap entry and each pop or push is $O(\log V)$. Space is $O(V)$ for distances plus up to $O(E)$ queued entries in the lazy variant. A Fibonacci heap improves the theoretical bound to $O(E + V\log V)$, though its constants rarely pay off in practice.

Worked example

The direct edge $0 \to 1$ has weight 4, but the detour $0 \to 2 \to 1$ costs only 3, so the shortest distance to 3 is 4:

W = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}
print(dijkstra(W, 0))   # {0: 0, 1: 3, 2: 1, 3: 4}

Follow-up questions

• Why must weights be nonnegative? The greedy 'first pop is final' invariant fails if a negative edge can later reduce a settled distance; use Bellman-Ford then.
• Why a heap instead of scanning for the minimum? A heap makes each extract-min and update $O(\log V)$, giving $O((V+E)\log V)$ rather than $O(V^2)$.
• How is Dijkstra related to BFS? It is BFS with a priority queue; with all weights equal it reduces exactly to BFS.
• How does A* extend Dijkstra? It adds an admissible heuristic to the priority key, focusing the search toward the goal.
• What handles negative weights or all-pairs? Bellman-Ford for negative edges; Floyd-Warshall for all-pairs shortest paths.

References

1. Dijkstra, A Note on Two Problems in Connexion with Graphs (1959).
2. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).
3. Hart, Nilsson & Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (A*, 1968).
4. Sedgewick & Wayne, Algorithms (4th ed.).