Dijkstra's Algorithm: Shortest Paths with a Priority Queue

Intuition First: Your GPS Finding the Fastest Route#

When your maps app finds the quickest way across a city, it doesn't try every possible route. It grows outward from where you are, always extending the cheapest road it hasn't committed to yet, and "locks in" each intersection in the order you can soonest reach it. Once an intersection is locked in, no later detour can possibly beat it, so the app never reconsiders it.

Dijkstra's algorithm is that strategy. Repeatedly settle the nearest unsettled place, relax the roads leading out of it, and the shortest path to everywhere falls out for free. The one catch (which the next article lifts) is that it assumes no road can have a negative cost.

---

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#

1. Assign distance 0 to the source vertex and ∞ to every other vertex.
2. Insert the source into a min-priority queue keyed by distance.
3. 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.
4. 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:

Source: A

Step	Pop	dist[A]	dist[B]	dist[C]	dist[D]
init	-	0	∞	∞	∞
1	A (d=0)	0	2	4	∞
2	B (d=2)	0	2	4	3
3	D (d=3)	0	2	4	3
4	C (d=4)	0	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, and that 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#

Let's take the example in this visualization: six weighted vertices A to F, source A, target E. The edge A-B weighs 4, but A-D weighs only 2 and D-B only 1, so watch B's tentative label drop from 4 to 3 the moment D is settled. That is a relaxation, and it can only happen while a vertex is still unsettled. Once B is popped at distance 3 it relaxes E to 3 + 3 = 6, E is popped next, and the run stops with the path A → D → B → E at total cost 6.

---

What to Remember#

• 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.