Exercise 3 solution

    import heapq

    def cheapest(g, start, goal):
        for node, edges in g.items():
            for nb, w in edges:
                if w < 0:
                    raise ValueError(f"negative weight on {node}->{nb}")
        best = {start: 0}
        parent = {start: None}
        heap = [(0, start)]
        while heap:
            d, cur = heapq.heappop(heap)
            if d > best[cur]:
                continue                     # stale entry
            if cur == goal:
                path = []
                while cur is not None:
                    path.append(cur)
                    cur = parent[cur]
                return d, path[::-1]
            for nb, w in g.get(cur, []):
                nd = d + w
                if nb not in best or nd < best[nb]:
                    best[nb] = nd
                    parent[nb] = cur
                    heapq.heappush(heap, (nd, nb))
        return None

    roads = {
        "A": [("B", 7), ("C", 2)],
        "B": [("D", 1)],
        "C": [("B", 3), ("D", 8), ("E", 5)],
        "D": [("F", 4)],
        "E": [("D", 2), ("F", 9)],
        "F": [],
        "Z": [("A", 1)],
    }
    print(cheapest(roads, "A", "F"))
    print(cheapest(roads, "A", "A"))
    print(cheapest(roads, "A", "Z"))
    print(cheapest(roads, "Z", "F"))

    try:
        cheapest({"A": [("B", -1)], "B": []}, "A", "B")
    except ValueError as e:
        print("error:", e)

Output:
    (10, ['A', 'C', 'B', 'D', 'F'])
    (0, ['A'])
    None
    (11, ['Z', 'A', 'C', 'B', 'D', 'F'])
    error: negative weight on A->B

The heap always hands back the unfinished node with the smallest known cost,
so the first time the goal is popped its cost cannot be beaten (provided no
weight is negative, which is why the function checks first). Entries are
never removed from the heap when a cheaper route is found; a stale entry is
simply skipped when it surfaces, which is the usual trick with heapq (see
Data Structures in Practice 6). Edges in Z point only outward, so "A" cannot
reach "Z" and the function returns None.

Checking it: the same function was compared against a slow, simple
relaxation algorithm on a random graph of 30 nodes and 120 weighted edges
(random.seed(5)), for every possible destination, and the costs matched in
all cases.