Dijkstra's Algorithm — Shortest Paths with a Priority Queue

The Concept

Dijkstra's algorithm solves the single-source shortest path problem: given a weighted graph with non-negative edge weights and a starting vertex, find the minimum-cost path from that vertex to every other reachable vertex.

The key insight is greedy: at every step, settle the unsettled vertex with the smallest known distance from the source. Once a vertex is settled, its distance is final — no later discovery can improve it (provided all weights are non-negative). This greedy property lets us avoid re-examining settled vertices.

How It Works

Assign distance 0 to the source vertex and ∞ to every other vertex.
Insert the source into a min-priority queue keyed by distance.
Repeatedly extract the vertex u with the smallest distance:
- If u has already been settled at a shorter distance, skip it (stale entry).
- For each neighbour v of u with edge weight w: if dist[u] + w < dist[v], update dist[v] and push (dist[u] + w, v) onto the queue.
Stop when the queue is empty. dist now holds the shortest distance from the source to every reachable vertex.

The "stale entry" check in step 3 handles a Python heapq subtlety: Python's heap has no efficient decrease-key operation, so we push a new entry instead of updating the existing one. The old (higher-distance) entry stays in the heap and is skipped when popped.

A Worked Example

Consider this graph:

plaintext

Source: A

Step	Pop	dist[B]	dist[C]	dist[D]
init	—	∞	∞	∞
1	A (d=0)	2	4	∞
2	B (d=2)	2	4	3
3	D (d=3)	2	4	3
4	C (d=4)	2	4	3

Final shortest paths from A: B=2, C=4, D=3.

Note that the path A→B→D (cost 3) beats the direct A→C→D path (cost 7) and even the direct A→C (cost 4) is not improved by going through D first.

Code Implementation

The graph parameter is an adjacency list where each entry is a list of (neighbour, weight) pairs — for example {'A': [('B', 2), ('C', 4)], ...}.

Complexity Analysis

Metric	Complexity	Notes
Time	O((V + E) log V)	Each vertex/edge can cause at most one heap push
Space	O(V + E)	Distance map + heap entries

With a Fibonacci heap, Dijkstra can achieve O(E + V log V), but binary-heap implementations are standard in practice and significantly simpler to code.

Why Negative Weights Break Dijkstra

The greedy settlement step is only safe because a shorter path to a settled vertex cannot be discovered later — which is only true when all weights are non-negative. With a negative-weight edge, a vertex that appears more expensive now could become cheaper once you travel down the negative edge, invalidating an already-settled distance.

If your graph has negative edge weights, use Bellman-Ford instead (covered in the next article). If it has no negative-weight cycles you can also convert negative weights using Johnson's algorithm, but Bellman-Ford is the simpler baseline.

Interactive Lab

Watch Dijkstra expand the shortest-path frontier one vertex at a time. The vertex popped from the priority queue is always the nearest unsettled vertex — its distance label turns permanent at that moment.

Simulation not available for this algorithm.

Key Takeaways

Greedy + priority queue. Always settle the closest unsettled vertex; its distance is then final.
Works only with non-negative weights. A negative edge can retroactively invalidate a settled distance.
O((V + E) log V) with a binary heap. Fast enough for millions of edges when combined with adjacency lists.
Real-world use. GPS routing (road networks), network routing protocols (OSPF), and game AI pathfinding all rely on Dijkstra or variants of it.
Lazy deletion for Python heaps. Since Python's heapq has no decrease-key, push updated entries and skip stale pops — the if d > dist.get(u, inf): continue guard handles this exactly.