Dijkstra's Algorithm

Dijkstra’s algorithm (Edsger Dijkstra, 1956) is the algorithm for finding shortest paths when edges have non-negative weights. It’s what your maps app is doing, conceptually, when it routes you across a city. If you learn one shortest-path algorithm cold, make it this one — every other weighted algorithm here is a variation on it.

The intuition

BFS explores in order of hop count. Dijkstra explores in order of total distance from the start. It repeatedly does one greedy thing:

Of all the nodes I haven’t finalized yet, take the one that is closest to the start, lock in its distance as final, and use it to improve its neighbors.

The magic is that “closest unfinalized node” can never be improved later — because every other route to it would have to pass through a node that’s farther away, and (with non-negative weights) adding more edges only adds cost. So once we pick it, its distance is settled forever.

The algorithm

Each node carries a tentative distance — the best total cost found so far, starting at $\infty$ for all nodes except the source (which is $0$). A min-priority queue always hands us the unfinalized node with the smallest tentative distance.

Dijkstra(graph, source):
    dist[source] ← 0
    dist[v] ← ∞ for every other v
    parent[v] ← none
    pq ← min-priority-queue holding (0, source)

    while pq is not empty:
        (d, u) ← pq.pop_min()          # closest unfinalized node
        if d > dist[u]:  continue      # stale entry — skip
        for each edge (u → v) with weight w:
            if dist[u] + w < dist[v]:  # ---- relaxation ----
                dist[v] ← dist[u] + w
                parent[v] ← u
                pq.push((dist[v], v))
    return dist, parent

The heart is the relaxation step (covered in the overview): “is going through u a cheaper way to reach v?” Everything else is just doing that in the right order — smallest tentative distance first.

Why the if d > dist[u]: continue line? Rather than update priorities in place (which most heaps don’t support cheaply), we push a new entry each time we improve a node and lazily ignore any outdated copies when they surface. This “lazy deletion” keeps the code simple and the complexity intact.

Worked example

Let’s route from A to F on our running graph. The highlighted edges below are the shortest-path tree Dijkstra builds; the thick blue route is the final A → F answer.

Watch the tentative distances settle. Each row is one “pop the closest node” step; bold = finalized that step, ∞ = not yet reached.

Step	Finalized	A	B	C	D	E	F
init	—	0	∞	∞	∞	∞	∞
1	A (0)	0	4	2	∞	∞	∞
2	C (2)	0	3	2	10	12	∞
3	B (3)	0	3	2	8	12	∞
4	D (8)	0	3	2	8	10	14
5	E (10)	0	3	2	8	10	13
6	F (13)	0	3	2	8	10	13

Trace two key moments:

• Step 2 — after finalizing C (distance 2), we relax C’s edges. B improves from $4$ to $2+1 = 3$: reaching B through C is cheaper than the direct A→B edge. This is why the path bends through C.
• Step 4 — finalizing D (distance 8) relaxes D→E to $8+2 = 10$, beating the earlier estimate of 12 (which came via C→E at cost $2+10$). E is corrected before it’s ever finalized.

Following parent pointers back from F: F ← E ← D ← B ← C ← A. Reverse it, and there’s the path.

Why it’s correct

The invariant: when a node is popped from the priority queue, its distance is final. Suppose not — suppose some node $u$ is popped with distance $\operatorname{dist}(u)$ but a shorter path $P$ exists. Path $P$ must leave the set of finalized nodes at some edge, reaching a first-unfinalized node $y$. But then $\operatorname{dist}(y) \le \operatorname{dist}(u)$ (since $P$ through $y$ is shorter and weights are non-negative), so the queue would have handed us $y$ before $u$ — contradiction.

That argument leans entirely on non-negative weights. With a negative edge, a longer-looking path could later become shorter, and a finalized node might need revising. Dijkstra can’t do that — for negative weights you need Bellman–Ford.

Complexity

With a binary heap as the priority queue, each of the $E$ edges can trigger a push, and each pop costs $O(\log V)$:

$$O((V + E)\log V) \text{ time}$$

A Fibonacci heap improves this to $O(E + V\log V)$ in theory, but its large constants mean a binary heap (or a d-ary heap) usually wins in practice. For dense graphs a simple array-based version runs in $O(V^2)$, which can beat the heap version when $E \approx V^2$.

Practical notes & pitfalls

• Stop early for single-pair queries. If you only need A → F, break the moment F is popped — everything about F is already final.
• No negative weights. Ever. Not even one. If you have them, switch algorithms; don’t try to “shift” weights to be positive — that changes which path is shortest.
• Lazy vs. eager deletion. The lazy version above (skip stale entries) is simplest. An eager version using an indexed/decrease-key heap avoids duplicate entries but needs a fancier structure.
• It explores outward in all directions. For long point-to-point routes that’s wasteful — half the explored nodes head away from the target. That’s the motivation for bidirectional Dijkstra and A*.