Dijkstra’s Algorithm with heapq in Python

Preamble

For weighted graphs with non-negative edges, Dijkstra computes single-source shortest paths. Python’s heapq is a min-heap perfect for the “extract minimum tentative distance” loop. This is the weighted counterpart to Breadth-First Search and Shortest Path Layers in Python’s BFS on unweighted graphs.

Sketch

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist.get(u, float("inf")):
            continue
        for v, w in graph.get(u, ()):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Represent graph[u] as (neighbor, weight) pairs.

Lazy deletion on the heap

heapq lacks decrease-key; duplicate heap entries are acceptable if you skip stale nodes when popped—classic lazy pattern. Alternatively reach for richer structures when profiling demands.

Conclusion

Negative edges need Bellman-Ford or Johnson; uniform costs still favor BFS. java.util.concurrent Primer for Python Developers introduces java.util.concurrent for Pythonistas heading into Java service work.