Dijkstra's shortest paths

Until now, every edge cost one step. Real routes have weights: minutes of driving, the price of a flight, the delay of a network link. Then the fewest edges aren't always the cheapest: one road of 10 minutes from A to B loses to three roads of 1 minute each, from A through C and D to B, though BFS would pick the single road. Dijkstra's algorithm finds the cheapest way from one start to every vertex, as long as no weight is negative. A weighted adjacency list keeps a pair for each edge, the neighbor and the weight.

Like BFS, with a heap

BFS takes the vertices in order of their number of steps. Dijkstra takes them in order of their distance, the total weight of the best way found so far, by keeping them in a heap of (distance, vertex) pairs: heapq pops the smallest pair, and pairs compare by their first item first.

1. The start has distance 0, and the heap holds (0, start).
2. Pop the closest pair, (d, v). If v already has a smaller distance, the pair is stale (more on that below): skip it. Otherwise d is v's final distance.
3. For each edge from v to w with weight cost, the way through v reaches w for d + cost. If w has no distance yet, or a bigger one, store the new one and push (d + cost, w). This is called relaxing the edge.

import heapq


def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, v = heapq.heappop(heap)
        if d > dist[v]:
            print("skip", v, d)
            continue
        print("take", v, d)
        for w, cost in graph[v]:
            if w not in dist or d + cost < dist[w]:
                dist[w] = d + cost
                heapq.heappush(heap, (d + cost, w))
    return dist


roads = {
    "A": [("B", 10), ("C", 1)],
    "B": [("A", 10), ("D", 1), ("E", 2)],
    "C": [("A", 1), ("D", 1)],
    "D": [("C", 1), ("B", 1), ("E", 7)],
    "E": [("B", 2), ("D", 7)],
}
print(dijkstra(roads, "A"))

take A 0
take C 1
take D 2
take B 3
take E 5
skip E 9
skip B 10
{'A': 0, 'B': 3, 'C': 1, 'D': 2, 'E': 5}

Skipping stale entries

heapq can't lower the distance of a pair that's already in the heap. So when a cheaper way to a vertex turns up, Dijkstra pushes a new pair and leaves the old one behind. B was pushed at 10 (straight from A) and later at 3 (through C and D), and E at 9 and then at 5. When an old pair finally comes out, its distance is bigger than dist[v]: it's stale, and continue skips it. Without that check the answers stay right, but every stale pair relaxes all the edges of its vertex again, for nothing.

Why it's right, and why no weight may be negative

When (d, v) is the smallest pair in the heap, could a cheaper way to v still be found later? That way would have to leave the vertices already taken through some vertex x that is still waiting in the heap, at a distance of at least d, and the edges after x only add to that. So it costs at least d, and d is final. That's also why a search for one goal can stop as soon as the goal comes out of the heap.

The argument needs "only add". A negative weight can make a later way cheaper, and then a distance taken as final isn't:

import heapq


def cheapest(graph, start, goal):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, v = heapq.heappop(heap)
        if v == goal:
            return d
        if d > dist[v]:
            continue
        for w, cost in graph[v]:
            if w not in dist or d + cost < dist[w]:
                dist[w] = d + cost
                heapq.heappush(heap, (d + cost, w))
    return None


graph = {"A": [("B", 2), ("C", 5)], "B": [], "C": [("B", -4)]}
print(cheapest(graph, "A", "B"))

2

B came out first, at 2, and was taken as final. But A, C, B costs 5 - 4 = 1. Graphs with negative weights need a slower algorithm, such as Bellman-Ford, O(V·E).

What it costs

Each edge pushes at most one pair, so the heap never holds more than E + 1 pairs, and each push and pop is O(log E), which is O(log V): E is at most V², so log E is at most 2 log V. In all, O((V + E) log V) time and O(V + E) memory.

The tempting way, trying every path and keeping the cheapest, explodes. In a ladder, two rows of vertices joined by rungs, each rung doubles the paths from one corner to the opposite one:

def count_paths(graph, v, goal, on_path):
    if v == goal:
        return 1
    on_path.add(v)
    total = 0
    for w in graph[v]:
        if w not in on_path:
            total += count_paths(graph, w, goal, on_path)
    on_path.remove(v)
    return total


def ladder(k):
    graph = {v: [] for v in range(2 * k)}
    for i in range(k):
        graph[i].append(k + i)
        graph[k + i].append(i)
    for i in range(k - 1):
        for v in [i, k + i]:
            graph[v].append(v + 1)
            graph[v + 1].append(v)
    return graph


for k in [4, 8, 12, 16]:
    print(k, "rungs:", count_paths(ladder(k), 0, 2 * k - 1, set()), "paths")

4 rungs: 8 paths
8 rungs: 128 paths
12 rungs: 2048 paths
16 rungs: 32768 paths

A ladder of 60 rungs has 2⁵⁹ paths, over 500 million billion: no computer gets through them. Dijkstra takes each of its 120 vertices once.