Shortest paths when edges have costs

Breadth-first search with a heap instead of a queue, and a precise reason why that works.

Key idea

Where breadth-first search fails

Breadth-first search is correct because the first arrival at a node is by the fewest edges, and with equal edge costs fewest edges means cheapest. Once edges have different costs those two stop being the same thing.

A path of one expensive edge can cost more than a path of three cheap ones. The queue reaches the one-edge path first and records it as the answer, which is simply wrong.

1# A to C directly costs 10. A to B to C costs 1 + 1 = 2.2edges = {"A": [("C", 10), ("B", 1)], "B": [("C", 1)], "C": []}3 4from collections import deque5def bfs_cost(start, goal):6    queue = deque([(start, 0)])7    seen = {start}8    while queue:9        node, cost = queue.popleft()10        if node == goal:11            return cost12        for nxt, weight in edges[node]:13            if nxt not in seen:14                seen.add(nxt)15                queue.append((nxt, cost + weight))16    return -117 18print(bfs_cost("A", "C"))          # finds the 10, not the 2

Why it works

Take the cheapest unfinished node, not the earliest

The repair is to change what comes out next. Instead of a queue handing back the earliest arrival, use a heap handing back the smallest known distance.

The invariant then becomes: when a node is popped, its recorded distance is final. Nothing still in the heap can improve it, because everything in the heap is at least that far away already and every edge adds a non-negative amount.

That sentence is the whole correctness argument, and it names its own precondition: edge costs must be non-negative. With a negative edge, a longer route could get cheaper later, and the guarantee collapses.

1import heapq2 3# Three ways to reach C, discovered in the order a search would find them.4heap = [(0, "A")]5heapq.heappush(heap, (10, "C"))          # the direct edge6heapq.heappush(heap, (1, "B"))7heapq.heappush(heap, (2, "C"))           # via B, found later and cheaper8 9print("pop order:", [heapq.heappop(heap) for _ in range(4)])

C surfaces twice. The cheap one comes out first, which is why the first pop of a node can be trusted and the second must be thrown away.

Trace it· 8 min

Trace the finalization order

Run the algorithm from A on edges A to C costing 10, A to B costing 1, B to C costing 1. For each pop give the node finalized and its final cost. Ignore stale pops that get skipped.

pop	node	final cost
1
2
3

Code lab· 30 min

Two shortest-path variants

cheapest_total returns the minimum total cost from a start to every reachable node. lowest_ceiling returns, for every reachable node, the smallest possible value of the largest edge on a path to it. Both take an adjacency map of node to a list of (neighbor, weight).

solution.py

Tests

graph = {    "A": [("B", 1), ("C", 10)],    "B": [("C", 1)],    "C": [],    "D": [],}print(cheapest_total(graph, "A"))print(lowest_ceiling(graph, "A"))print(cheapest_total(graph, "D"))

Output

Run tests to see output.

Problem· 28 min

Network Delay Time

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 30 min

Swim In Rising Water

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1# A to C directly costs 10. A to B to C costs 1 + 1 = 2.2edges = {"A": [("C", 10), ("B", 1)], "B": [("C", 1)], "C": []}3 4from collections import deque5def bfs_cost(start, goal):6 queue = deque([(start, 0)])7 seen = {start}8 while queue:9 node, cost = queue.popleft()10 if node == goal:11 return cost12 for nxt, weight in edges[node]:13 if nxt not in seen:14 seen.add(nxt)15 queue.append((nxt, cost + weight))16 return -117 18print(bfs_cost("A", "C")) # finds the 10, not the 2

1import heapq2 3# Three ways to reach C, discovered in the order a search would find them.4heap = [(0, "A")]5heapq.heappush(heap, (10, "C")) # the direct edge6heapq.heappush(heap, (1, "B"))7heapq.heappush(heap, (2, "C")) # via B, found later and cheaper8 9print("pop order:", [heapq.heappop(heap) for _ in range(4)])

pop

node

final cost