Graph Algorithms

Shortest paths: Dijkstra

The priority-queue BFS for weighted edges

~12 minLesson 23 of 25Written by Claude Opus 4.8

A weighted graph asks a harder question than an unweighted one: not how few edges to a destination, but how little total distance. BFS - which fans out by edge count - gives the wrong answer the moment edges have different costs. Dijkstra's algorithm fixes this with one greedy habit: always finalize the closest unsettled node next, powered by the priority queue you built earlier. It is the routing engine behind map directions, network packets, and a great deal more.

The shortest-path problem

On a weighted graph the length of a path is the sum of its edge weights, and the shortest path between two nodes is the one with the smallest total. Dijkstra solves the single-source version: from one start node, find the shortest distance to every other node at once. It keeps two arrays - $dist [v]$ , the best distance known so far, and $pred [v]$ , the node you arrived from - and grows a tree of finalized ("settled") nodes outward from the source.

Relax, settle, repeat

The whole algorithm is a loop over two moves. Settle the closest unsettled node, then relax each edge leaving it. Relaxation is the only place distances ever change.

Edge relaxation

For an edge $u \to v$ of weight $w$ , ask: is the route to $v$ through $u$ shorter than the best route found so far?

dist [v] \leftarrow min (dist [v], dist [u] + w (u, v)) .

If it is, we lower $dist [v]$ and record $pred [v] = u$ , so the path can be rebuilt later. Dijkstra's discipline is to relax edges only out of the closest unsettled node, and to trust that node's distance as final the instant it is chosen. The priority queue exists to answer one question fast, over and over: which unsettled node has the smallest $dist$ ?

Watch it settle the graph

Below is a fixed directed graph with weights on every edge; the source is A. Step through it. Each step extracts the minimum from the priority queue (amber, right), settles that node (it turns green), and relaxes its out-edges - distance labels drop as shorter routes are found, and the shortest-path tree grows in teal. When you reach the end, flip the toggle to make one edge negative and step again: Dijkstra will confidently return a wrong answer.

Dijkstra from A extract-min - relax - settle

D→F = +2all weights ≥ 0

Priority queue - min pops next

Settled - distance is final

none yet

Initialize: dist[A] = 0, every other node = ∞, pred all empty. The priority queue holds only the source, A.

node	A	B	C	D	E	F
dist	0	∞	∞	∞	∞	∞
pred	-	-	-	-	-	-

Path to F: not reached yet.

Why grabbing the closest node works

When $u$ is the minimum-distance node left in the queue, any other path to $u$ must first leave the settled region through some node already in the queue whose distance is $\geq dist [u]$ . Because every remaining edge weight is $\geq 0$ , that detour can only add length - it can never beat $dist [u]$ . So $dist [u]$ is already optimal and $u$ can be settled forever. That one sentence is the entire correctness proof - and it is exactly where the non-negative-weight assumption is load-bearing.

One negative edge and it lies

Flip the toggle to give edge $D \to F$ a weight of $- 5$ , then step to the end. At step 5, relaxing $D \to F$ finds $6 + (- 5) = 1$ , cheaper than $F$ 's settled $4$ - but $F$ was finalized two steps earlier, and Dijkstra never reopens a settled node. It reports $dist [F] = 4$ ; the true shortest is $A \to B \to C \to D \to F = 1$ . The greedy invariant assumed a detour could only add length; a negative edge breaks it. For graphs with negative weights, use Bellman-Ford ( $O (V E)$ ) instead, which relaxes every edge $V - 1$ times and makes no greedy commitment.

The code

A faithful implementation is barely twenty lines. The priority queue is Python's heapq (a binary min-heap); the one subtlety is lazy deletion - instead of updating an entry's key in place, we push a fresh, smaller pair and skip any stale pair we later pop.

import heapq

def dijkstra(graph, src):            # graph: {u: [(v, w), ...]}, every w >= 0
    dist = {u: float("inf") for u in graph}
    pred = {u: None for u in graph}
    dist[src] = 0
    pq = [(0, src)]                     # min-heap of (distance, node)
    while pq:
        d, u = heapq.heappop(pq)       # extract the closest unsettled node
        if d > dist[u]:               # stale entry - a better one was queued later
            continue
        for v, w in graph[u]:          # relax every edge out of u
            nd = d + w
            if nd < dist[v]:          # found a shorter route to v
                dist[v] = nd
                pred[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, pred

def path(pred, src, target):          # rebuild a route by walking predecessors
    route = []
    while target is not None:
        route.append(target)
        target = pred[target]
    route.reverse()
    return route if route and route[0] == src else []

Where O(E log V) comes from

Each edge, when it improves a distance, pushes one $(dist, v)$ pair onto the heap - at most $O (E)$ pushes, each costing $O (lo g V)$ . We pop $O (V + E)$ times, each $O (lo g V)$ . A popped pair whose stored distance exceeds the current $dist [v]$ is stale (a better one was queued afterward), so we discard it in $O (1)$ - that is the if d > dist[u]: continue line. Adding it up gives $O ((V + E) lo g V)$ , which is $O (E lo g V)$ on a connected graph. A plain array-scan for the minimum instead costs $O (V^{2})$ - better only for dense graphs.

Check yourself

Why can a single negative-weight edge make Dijkstra return a wrong distance?

With a binary-heap priority queue, Dijkstra's running time is:

Recall: what does Dijkstra do each step, and what must be true of every edge weight?

Recall the loop invariant. Try to state it, then check.

Lock it in

Dijkstra solves single-source shortest paths on non-negative weighted graphs with a greedy loop: settle the closest unsettled node, then relax its out-edges.
Relaxation is the only place distances change: $dist [v] = min (dist [v], dist [u] + w)$ , recording $pred [v]$ so the path can be rebuilt.
Grabbing the closest node is safe only because every weight is $\geq 0$ ; a single negative edge breaks it, so reach for Bellman-Ford ( $O (V E)$ ).
With a binary-heap priority queue answering extract-min, the whole thing runs in $O (E lo g V)$ .

Primary source

Work through the algorithm and its proof with Abdul Bari - Dijkstra's algorithm, then build your own weighted graphs and watch the priority queue drive it step by step at VisuAlgo - Single-Source Shortest Paths.

Ask your teacher

The priority queue steering Dijkstra is the binary heap you built earlier - same extract-min, same $O (lo g V)$ per operation. And the same best-first machinery reappears in LLM decoding as beam search: it keeps the top- $k$ highest-scoring partial sequences on a bounded priority queue and expands the most promising first, exactly as Dijkstra expands the closest node first. That bridge is traced in priority queues and Dijkstra to beam search in the LLM course. Want to see how beam search differs - a fixed-width frontier and a scoring rule that can't guarantee the global optimum? Ask, and I'll build the follow-up.