Shortest Paths (Dijkstra)

BFS is perfect when every edge costs the same: the first time you reach a node, you reached it by the fewest hops, and fewest hops is shortest. But give the edges weights — a toll road costs more than a side street, a slow link adds more latency than a fast one — and BFS falls apart. It cannot tell four cheap edges from four expensive ones.

Dijkstra’s algorithm fixes this with a single, almost stubborn rule: always step out from the cheapest-to-reach node you have found so far. That one greedy choice, backed by a priority queue, builds the correct least-cost path to every node.

The notepad picture

Imagine driving across a city where some roads have tolls. You keep a notepad, and for every intersection you have reached you write down the cheapest known cost to get there. When you must move, you leave from the intersection with the smallest total on your pad — not the one nearest in distance, the one cheapest-to-reach. Leaving a node, you do two things. First you lock its cost in: because no edge is negative, no later detour can beat the cheapest route you already hold to it. Then you relax its neighbours — for each one, check whether coming through this node is cheaper than its current note, and if so, lower it. That check-and-lower step, relaxation, is the whole engine.

The implementation

Relaxation in one line is if dist[u] + w < dist[v]: dist[v] = dist[u] + w. Dijkstra’s only other need is a fast answer to “which unvisited node is cheapest?” — and that is exactly what a min-heap gives, in O(log V). Push (distance, node) tuples and the heap orders them for you:

import heapq

def dijkstra(graph, source):
    dist = {n: float("inf") for n in graph}
    prev = {n: None for n in graph}
    dist[source] = 0
    heap = [(0, source)]                         # (tentative distance, node)

    while heap:
        d, u = heapq.heappop(heap)               # cheapest unfinalised node
        if d > dist[u]:
            continue                             # a stale, superseded entry
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:            # relaxation
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev

def path_to(prev, target):
    out = []
    while target is not None:
        out.append(target)
        target = prev[target]
    return " -> ".join(reversed(out))

graph = {
    "A": [("B", 4), ("D", 7)],
    "B": [("A", 4), ("C", 3), ("D", 2)],
    "C": [("B", 3), ("E", 2), ("F", 5)],
    "D": [("A", 7), ("B", 2), ("E", 3)],
    "E": [("D", 3), ("C", 2), ("F", 6)],
    "F": [("C", 5), ("E", 6)],
}
dist, prev = dijkstra(graph, "A")
for node in sorted(dist):
    print(f"A -> {node}: cost {dist[node]:<2} via {path_to(prev, node)}")

A -> A: cost 0  via A
A -> B: cost 4  via A -> B
A -> C: cost 7  via A -> B -> C
A -> D: cost 6  via A -> B -> D
A -> E: cost 9  via A -> B -> D -> E
A -> F: cost 12 via A -> B -> C -> F

Look at D: the direct edge from A costs 7, but Dijkstra finds the cheaper A → B → D at 6, because it expanded B (cost 4) before ever finalising D. A node becomes final the instant it is popped — and the if d > dist[u]: continue guard quietly throws away the stale heap entries left behind when a shorter route was found first.

The shortest-path family

A* is Dijkstra plus a heuristic estimate of the distance still to go; if that estimate never overestimates, A* finds the shortest path while exploring far fewer nodes — which is why your navigation app uses it. Anywhere you have a weighted graph and ask “what is the cheapest route from X to Y” — IP routing, CDN latency, map directions — Dijkstra is the starting point.

Practice