Dijkstra's Algorithm: Shortest Paths with a Priority Queue

Your maps app finding a route, a network router choosing where to forward a packet, a game character walking around obstacles: they're all versions of the same question. Given a graph with weighted edges, what's the cheapest path from here to everywhere else?

For unweighted graphs, breadth-first search answers it: explore one step away, then two, then three. Weights break that. A path with three cheap edges can beat one with a single expensive edge, so "fewest steps" is no longer "shortest". Dijkstra's algorithm, published by Edsger Dijkstra in 1959, fixes this by always expanding the closest unfinished node next.

This article builds it in Python, traces it on a real graph, explains why it works, and covers the details that separate a textbook version from one you can trust: stale heap entries, ties, negative weights and complexity. You should be comfortable with Big-O (Big-O Notation Explained with Real Code) and with Python dictionaries.

The example graph#

Six places joined by roads, each road labelled with its travel time. Roads go both ways.

We'll store it as an adjacency map: for each node, a dictionary of neighbours and edge weights.

from collections import defaultdict

edges = [("A", "B", 4), ("A", "C", 2), ("B", "C", 1), ("B", "D", 5), ("C", "D", 8),
         ("C", "E", 10), ("D", "E", 2), ("D", "F", 6), ("E", "F", 2)]

graph = defaultdict(dict)
for u, v, w in edges:
    graph[u][v] = w
    graph[v][u] = w      # undirected: add both directions

The idea#

Keep a tentative distance for every node: 0 for the source, infinity for everything else. Then repeat:

1. Pick the unfinished node with the smallest tentative distance. Its distance is now final.
2. Relax each of its edges: if going through this node gives a neighbour a shorter distance than the one it has, update the neighbour.

The only hard part is step 1: finding the smallest distance quickly. Scanning every node each time costs O(V) per step. A priority queue (a binary heap) gets it down to O(log V).

The implementation#

Python's heapq module turns a plain list into a min-heap. It has no "decrease key" operation, so when a node's distance improves we simply push a new entry and leave the old one in the heap. When the old one eventually comes out, we recognise it as stale and skip it. This is called lazy deletion, and it's how almost every Python implementation works.

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    prev = {}                             # prev[node] = the node we reached it from
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                      # stale entry: we already found a shorter way here
        for neighbor, weight in graph[node].items():
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float("inf")):
                dist[neighbor] = new_dist
                prev[neighbor] = node
                heapq.heappush(heap, (new_dist, neighbor))
    return dist, prev

>>> dist, prev = dijkstra(graph, "A")
>>> dist
{'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 12}

Nodes that can't be reached from the source simply don't appear in dist.

Rebuilding the path#

dist gives the length of each shortest path; prev lets us rebuild the path itself by walking backwards from the target:

def path_to(prev, source, target):
    path = [target]
    while path[-1] != source:
        path.append(prev[path[-1]])       # KeyError means target is unreachable
    return path[::-1]

>>> path_to(prev, "A", "F")
['A', 'C', 'B', 'D', 'E', 'F']

The prev pointers form a shortest-path tree rooted at the source: the highlighted edges in the diagram. Notice that the best route to B isn't the direct road (4) but the detour through C (2 + 1 = 3).

A step-by-step trace#

Here's every heap operation for our graph. Watch for the stale entries: B, D, E and F each get pushed twice because a shorter route turned up after the first push.

Why it's correct#

The key claim is: when a node is popped with its current distance d, no shorter path to it exists.

Suppose a shorter path did exist. It starts at the source (already settled) and ends at our node, so somewhere along it there's a first node that isn't settled yet; call it u. The part of the path before u runs through settled nodes, so u was relaxed with that distance and sits in the heap with a key no larger than the length of the path up to u. Since every edge weight is non-negative, the remaining edges can only add to that, so u's key is at most the shorter path's length, which is less than d. But then the heap would have given us u before our node. Contradiction.

That argument leans on exactly one assumption: non-negative weights. Take it away and the whole thing falls apart.

Negative edges break it#

graph = {"A": {"B": 2, "C": 3}, "B": {"D": 2}, "C": {"B": -2}, "D": {}}

The true distance to B is 1 (A → C → B), and to D it's 3. But Dijkstra pops B (distance 2) before C (distance 3), so it considers B finished before the cheaper route through C has been seen. Textbook versions that mark nodes as "done" return B = 2 and D = 4, which is wrong.

Our lazy version happens to fix itself here, because it re-pushes B when the shorter distance shows up and then processes B again. Don't rely on that: with negative edges a node can be re-processed many times, and on adversarial graphs the running time becomes exponential. If your graph can have negative weights, use the Bellman–Ford algorithm (O(V·E)), which also detects negative cycles, where no shortest path exists at all.

Complexity#

Every node is processed only once (later entries for it are skipped as stale), so each edge is relaxed at most once in each direction and causes at most one push. The heap therefore holds O(E) entries, and every push and pop costs O(log E). Since E is at most V², log E is at most 2 log V, which gives:

• Time: O((V + E) log V) with a binary heap.
• Space: O(V + E) for the graph, the distances and the heap.

For dense graphs, where E is close to V², a simpler O(V²) version without a heap is actually faster: keep an array of distances and scan it for the minimum each time. Theoretical structures like Fibonacci heaps reach O(E + V log V), but their overhead rarely pays off in practice.

Practical details#

Stop early. If you only need the path to one target, return as soon as you pop it. Its distance is final at that moment, and on a big graph you can skip most of the work:

        d, node = heapq.heappop(heap)
        if node == target:
            return d

Ties in the heap. Heap entries are tuples, so when two distances are equal Python compares the nodes themselves. That's fine for strings and numbers, but node objects that don't support < raise TypeError. Add a counter as a tiebreaker:

from itertools import count

tiebreak = count()
heapq.heappush(heap, (new_dist, next(tiebreak), neighbor))

Floating-point weights. With float weights, two routes of "equal" length can differ by rounding errors. Compare with a tolerance, or scale to integers (centimetres, milliseconds), when the exact path matters.

Where to go from here#

• A* is Dijkstra plus a heuristic: it orders the heap by distance + estimate_to_target. With a good estimate (like straight-line distance on a map) it explores far fewer nodes while still finding the shortest path, as long as the estimate never overestimates.
• Network routing uses Dijkstra directly: OSPF routers compute shortest paths over the network map with it.
• Road networks at continental scale use preprocessing techniques such as contraction hierarchies, with Dijkstra-style searches at their core.

Recap#

• Dijkstra finds shortest paths from one source in graphs with non-negative edge weights.
• Always expand the closest unfinished node; a min-heap (heapq) finds it in O(log V).
• Without decrease-key, push duplicates and skip stale entries (if d > dist[node]: continue).
• Keep prev pointers to rebuild paths; they form a shortest-path tree.
• Runs in O((V + E) log V); use Bellman–Ford for negative edges and an O(V²) array scan for very dense graphs.