Dijkstra's algorithm with a heap

Dijkstra’s algorithm finds the cheapest route from one start node to every other node of a graph whose edges carry costs, provided no cost is negative. It keeps the cheapest cost found so far for every node and a min-heap of candidates. Again and again it takes the cheapest candidate out of the heap: that node’s cost is now final, so the algorithm settles it and tries every edge leaving it, lowering a neighbour’s cost whenever the edge gives a cheaper route. That step is called relaxing the edge. With a binary heap, a graph of V nodes and E edges takes O((V + E) log V) time. Use it for tolls, travel times, prices and any other cost that is zero or positive. When every edge costs the same, breadth-first search is simpler, and when some costs are negative, Dijkstra’s algorithm can return wrong answers.

This lesson builds the version that coding rounds use, with lazy deletion: a node that gets cheaper is pushed again, and its old, stale entry is skipped when it comes out. It counts what the heap does on four graphs, breaks the algorithm with one negative edge, and solves a problem in full, the cheapest delivery route through a toll network, from the brute force to code in Python, JavaScript, Java, C++ and Go.

When Dijkstra’s algorithm fits

Three signs in a statement point to it:

• Edges have a cost, and the question asks for the cheapest, fastest or shortest total: tolls on roads, minutes on train links, fees on currency conversions, metres of cable.
• Every cost is zero or positive. A route then never gets cheaper as it grows longer, which is the one property the algorithm relies on.
• There is one starting point, or several that all start at cost 0, and the answer is a cost for one target or for every node.

Breadth-first search, from the lesson on modelling problems as graphs, is the special case in which every edge costs 1: its queue reaches nodes in order of distance only because the costs are equal. When they differ, the route with the fewest edges is not always the cheapest. The two searches compare like this:

The third standard search for a single start, Bellman–Ford, accepts negative costs too and reports a cycle whose total is negative, at a price of O(V · E); refunds and limits on the number of edges call for it.

Settling the cheapest node first

Picture the start node with cost 0 and every other node with an unknown cost, written as infinity. The nodes fall into two groups: settled nodes, whose cheapest cost is known for certain, and the rest, each holding the cheapest cost found so far, its tentative cost. Each step does two things:

1. Among the nodes not yet settled, pick the one with the smallest tentative cost, and settle it.
2. Relax every edge u → v leaving the node u that was just settled: if the cost of u plus the cost of the edge is less than v’s tentative cost, lower v’s cost to that sum and record u as v’s parent, the node v is best reached from.

Why may the cheapest unsettled node be settled? Every route to it from the start must leave the settled group somewhere, and every node just outside that group already costs at least as much as the node being settled. With no negative edges, the rest of such a route can only add cost, so no route found later can be cheaper. The section on correctness below turns this into a proof.

Edsger W. Dijkstra published the method in a three-page note in 1959, beside a method for the shortest spanning tree of a graph. His version keeps no heap: it scans all the unsettled nodes for the cheapest one, which costs O(V²) in all. Coding rounds use a binary heap instead, so that finding the cheapest candidate costs O(log V).

The template, with lazy deletion

Python’s heapq, Java’s PriorityQueue and C++’s std::priority_queue have no operation that lowers the cost of an entry already in the heap. Python’s documentation describes the way round it for priority queues in general: mark the old entry as removed and add a new one. Dijkstra’s algorithm does not even need the mark. When a node gets cheaper, the code pushes a new entry and leaves the old one in place; once the old one reaches the top, its cost is larger than the node’s recorded cost, so it is stale and is skipped. Here is the whole algorithm on a graph of five nodes, printing every step:

"""Dijkstra's algorithm with a binary heap and lazy deletion, traced on a graph of five nodes."""
import heapq
import math

# One-way edges (from, to, cost).
EDGES = [(0, 1, 6), (0, 2, 2), (2, 1, 3), (1, 3, 1), (2, 3, 7), (3, 4, 2)]


def dijkstra(n, edges, s):
    """The cheapest cost from s to every node (math.inf where s cannot reach)."""
    out = [[] for _ in range(n)]
    for u, v, cost in edges:
        out[u].append((v, cost))
    dist = [math.inf] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            print(f"pop ({d}, {u})  stale: {u} was reached for {dist[u]}")
            continue
        print(f"pop ({d}, {u})  settle {u}")
        for v, cost in out[u]:
            if d + cost < dist[v]:  # relax the edge u -> v
                dist[v] = d + cost
                heapq.heappush(heap, (dist[v], v))
                print(f"    push ({dist[v]}, {v})")
    return dist


print("dist:", dijkstra(5, EDGES, 0))

pop (0, 0)  settle 0
    push (6, 1)
    push (2, 2)
pop (2, 2)  settle 2
    push (5, 1)
    push (9, 3)
pop (5, 1)  settle 1
    push (6, 3)
pop (6, 1)  stale: 1 was reached for 5
pop (6, 3)  settle 3
    push (8, 4)
pop (8, 4)  settle 4
pop (9, 3)  stale: 3 was reached for 6
dist: [0, 5, 2, 6, 8]

// Dijkstra's algorithm with a binary heap and lazy deletion, traced on a graph of five nodes.
// JavaScript has no heap in its standard library, so a small one comes first: entries are
// [cost, node] pairs, smallest cost first, and the smaller node first on a tie (as Python's tuples).

class MinHeap {
  constructor() {
    this.a = [];
  }
  get size() {
    return this.a.length;
  }
  static less(x, y) {
    return x[0] < y[0] || (x[0] === y[0] && x[1] < y[1]);
  }
  push(item) {
    const a = this.a;
    a.push(item);
    for (let i = a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (!MinHeap.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && MinHeap.less(a[l], a[m])) m = l;
        if (r < a.length && MinHeap.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

// One-way edges [from, to, cost].
const EDGES = [[0, 1, 6], [0, 2, 2], [2, 1, 3], [1, 3, 1], [2, 3, 7], [3, 4, 2]];

function dijkstra(n, edges, s) {
  const out = Array.from({ length: n }, () => []);
  for (const [u, v, cost] of edges) out[u].push([v, cost]);
  const dist = new Array(n).fill(Infinity);
  dist[s] = 0;
  const heap = new MinHeap();
  heap.push([0, s]);
  while (heap.size > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) {
      console.log(`pop (${d}, ${u})  stale: ${u} was reached for ${dist[u]}`);
      continue;
    }
    console.log(`pop (${d}, ${u})  settle ${u}`);
    for (const [v, cost] of out[u]) {
      if (d + cost < dist[v]) { // relax the edge u -> v
        dist[v] = d + cost;
        heap.push([dist[v], v]);
        console.log(`    push (${dist[v]}, ${v})`);
      }
    }
  }
  return dist;
}

console.log(`dist: [${dijkstra(5, EDGES, 0).join(", ")}]`);

pop (0, 0)  settle 0
    push (6, 1)
    push (2, 2)
pop (2, 2)  settle 2
    push (5, 1)
    push (9, 3)
pop (5, 1)  settle 1
    push (6, 3)
pop (6, 1)  stale: 1 was reached for 5
pop (6, 3)  settle 3
    push (8, 4)
pop (8, 4)  settle 4
pop (9, 3)  stale: 3 was reached for 6
dist: [0, 5, 2, 6, 8]

Read the trace from the top:

1. The start goes in at cost 0. dist holds the cheapest cost found so far for every node, infinity for nodes not reached yet, and the heap holds (cost, node) pairs, cheapest first.
2. Settling node 0 relaxes its two edges: node 1 for 6 and node 2 for 2.
3. Settling node 2 reaches node 1 again, for 2 + 3 = 5, which beats 6: dist[1] becomes 5 and (5, 1) goes in. The entry (6, 1) stays in the heap.
4. (5, 1) comes out before (6, 1). When (6, 1) reaches the top later, 6 is more than dist[1], so the line if d > dist[u] skips it. That one comparison is the whole of lazy deletion.
5. Node 3 goes the same way: (9, 3) from node 2, then (6, 3) from node 1, and the stale (9, 3) is the last entry out.

Seven entries came out of the heap, and two of them were stale. A node is settled once, when an entry with its current cost comes out, and its edges are relaxed only then. Every push follows one successful relaxation, so the heap never receives more than E + 1 entries: at most one per edge, plus the start.

The JavaScript tab begins with a binary heap of about 35 lines, because JavaScript’s standard library has none. It breaks ties by node number, as Python’s tuples do, so both tabs print the same trace.

What it costs, counted

Every settled node reads its list of edges once, which is O(V + E) in all. On top of that, every push and every pop moves an entry up or down the heap, through at most log₂ of its size in levels. The program below runs the template on four graphs and counts the heap’s work:

"""The work of Dijkstra's algorithm, counted: heap operations on three graphs, then the array version on the dense one."""
import heapq
import math
import random


def dijkstra_counted(n, out, s):
    """Lazy-deletion Dijkstra that counts its pushes, pops, stale pops and the largest heap."""
    dist = [math.inf] * n
    dist[s] = 0
    heap = [(0, s)]
    pushes, pops, stale, largest = 1, 0, 0, 1
    while heap:
        d, u = heapq.heappop(heap)
        pops += 1
        if d > dist[u]:
            stale += 1
            continue
        for v, w in out[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
                pushes += 1
                largest = max(largest, len(heap))
    return dist, pushes, pops, stale, largest


def dijkstra_array(n, out, s):
    """Dijkstra's O(n^2) form: no heap, a scan of every node for the closest one not yet settled."""
    dist = [math.inf] * n
    dist[s] = 0
    done = [False] * n
    scans = 0
    for _ in range(n):
        u = -1
        for v in range(n):
            scans += 1
            if not done[v] and (u < 0 or dist[v] < dist[u]):
                u = v
        if dist[u] == math.inf:
            break
        done[u] = True
        for v, w in out[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist, scans


def grid(side, rng):
    """A side x side grid, every cell joined to its 4 neighbours; each one-way step costs 1 to 9."""
    n = side * side
    out = [[] for _ in range(n)]
    for r in range(side):
        for c in range(side):
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                rr, cc = r + dr, c + dc
                if 0 <= rr < side and 0 <= cc < side:
                    out[r * side + c].append((rr * side + cc, rng.randint(1, 9)))
    return n, out


def sparse(n, m, rng):
    """n nodes and m one-way edges between random nodes, each costing 1 to 1,000."""
    out = [[] for _ in range(n)]
    for _ in range(m):
        out[rng.randrange(n)].append((rng.randrange(n), rng.randint(1, 1000)))
    return n, out


def complete(n, rng):
    """Every ordered pair of n nodes joined by a one-way edge costing 1 to 1,000."""
    return n, [[(v, rng.randint(1, 1000)) for v in range(n) if v != u] for u in range(n)]


def complete_worst(n):
    """A complete graph whose costs make every edge from a settled node lower a later node's distance:
    u -> v costs 2(v - u) - 1 when u < v, so nodes settle in the order 0, 1, 2, ... at distances 0, 1, 2, ..."""
    return n, [[(v, 2 * (v - u) - 1 if u < v else n * n) for v in range(n) if v != u] for u in range(n)]


rng = random.Random(23)
graphs = [("grid 300 x 300", grid(300, rng)), ("sparse, 100,000 nodes", sparse(100_000, 300_000, rng)),
          ("complete, 1,000 nodes", complete(1_000, rng)), ("complete, 1,000 nodes, worst costs", complete_worst(1_000))]
for name, (n, out) in graphs:
    e = sum(len(x) for x in out)
    dist, pushes, pops, stale, largest = dijkstra_counted(n, out, 0)
    reached = sum(d < math.inf for d in dist)
    print(f"{name}: V = {n:,}, E = {e:,}, reached {reached:,}")
    print(f"  pushes {pushes:,} (at most E + 1 = {e + 1:,}), pops {pops:,}, stale {stale:,}, largest heap {largest:,}")
    print(f"  heap operations {pushes + pops:,}; each sifts at most {math.ceil(math.log2(largest + 1))} levels")

n, out = graphs[3][1]
dist_array, scans = dijkstra_array(n, out, 0)
assert dist_array == dijkstra_counted(n, out, 0)[0]
print(f"array version on the worst complete graph: {scans:,} scans and {sum(len(x) for x in out):,} edge checks, no heap")

grid 300 x 300: V = 90,000, E = 358,800, reached 90,000
  pushes 112,312 (at most E + 1 = 358,801), pops 112,312, stale 22,312, largest heap 744
  heap operations 224,624; each sifts at most 10 levels
sparse, 100,000 nodes: V = 100,000, E = 300,000, reached 94,051
  pushes 111,754 (at most E + 1 = 300,001), pops 111,754, stale 17,703, largest heap 37,006
  heap operations 223,508; each sifts at most 16 levels
complete, 1,000 nodes: V = 1,000, E = 999,000, reached 1,000
  pushes 6,181 (at most E + 1 = 999,001), pops 6,181, stale 5,181, largest heap 5,609
  heap operations 12,362; each sifts at most 13 levels
complete, 1,000 nodes, worst costs: V = 1,000, E = 999,000, reached 1,000
  pushes 499,501 (at most E + 1 = 999,001), pops 499,501, stale 498,501, largest heap 333,000
  heap operations 999,002; each sifts at most 19 levels
array version on the worst complete graph: 1,000,000 scans and 999,000 edge checks, no heap

On the first three graphs only a fraction of the edges ever lowers a cost: about one in three on the grid and on the sparse graph, and about one in 160 on the complete graph with random costs, where the cheap edges out of the start already reach most nodes for little. The fourth graph is built so that every edge from a settled node to a later node is a cheaper route: u → v costs 2(v − u) − 1. Then half of all edges push an entry, the heap grows to a third of a million entries, and each push or pop may sift through 19 levels, up to about 19 million steps in all, an upper estimate from the counts. Dijkstra’s original array version does 1,000 scans of 1,000 nodes on the same graph, a million steps, with no heap at all.

So the binary heap pays off on sparse graphs, where E is a small multiple of V. Grids, road networks and flight maps, which is most interview input, are sparse. On a dense graph, with E close to V², the O(V²) array version can be faster. A Fibonacci heap brings the bound down to O(E + V log V), as Fredman and Tarjan showed in 1987, but its constant factors make it rare in practice and in interviews.

Why negative costs break it

The argument for settling the cheapest node assumed that a route never gets cheaper as it grows. A negative cost, such as a refund on a road, breaks exactly that. The program runs two versions on four nodes with one refund: the textbook version, which never touches a node again once it is settled, and this lesson’s template:

"""One negative edge, two versions of Dijkstra: the one that settles each node once gives a wrong answer."""
import heapq
import math

# 0 -> 1 costs 2, 0 -> 2 costs 5, 2 -> 1 costs -4 (a refund), 1 -> 3 costs 1.
EDGES = [(0, 1, 2), (0, 2, 5), (2, 1, -4), (1, 3, 1)]
N = 4


def adjacency(n, edges):
    out = [[] for _ in range(n)]
    for u, v, cost in edges:
        out[u].append((v, cost))
    return out


def settle_once(n, edges, s):
    """The textbook form: a node is settled when it is popped, and settled nodes are never relaxed again."""
    out = adjacency(n, edges)
    dist, done, pops = [math.inf] * n, [False] * n, []
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if done[u]:
            continue
        done[u] = True
        pops.append(u)
        for v, cost in out[u]:
            if not done[v] and d + cost < dist[v]:
                dist[v] = d + cost
                heapq.heappush(heap, (dist[v], v))
    return dist, pops


def lazy(n, edges, s):
    """The lesson's form: skip only stale entries, so a node whose distance drops is popped again."""
    out = adjacency(n, edges)
    dist, pops = [math.inf] * n, []
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        pops.append(u)
        for v, cost in out[u]:
            if d + cost < dist[v]:
                dist[v] = d + cost
                heapq.heappush(heap, (dist[v], v))
    return dist, pops


for name, run in [("settle once", settle_once), ("lazy", lazy)]:
    dist, pops = run(N, EDGES, 0)
    print(f"{name:12} dist {dist}   nodes expanded, in order: {pops}")
print("true cost of 0 -> 3: 0 -> 2 -> 1 -> 3 = 5 - 4 + 1 =", 5 - 4 + 1)

settle once  dist [0, 2, 5, 3]   nodes expanded, in order: [0, 1, 3, 2]
lazy         dist [0, 1, 5, 2]   nodes expanded, in order: [0, 1, 3, 2, 1, 3]
true cost of 0 -> 3: 0 -> 2 -> 1 -> 3 = 5 - 4 + 1 = 2

The cheapest route from 0 to 3 goes 0 → 2 → 1 → 3, for 5 − 4 + 1 = 2. The textbook version settles node 1 at cost 2 through the direct edge, settles node 3 at 3, and only then reaches node 2, whose refund would make node 1 cheaper. Node 1 is settled already, so it is left alone, and node 3 stays at 3: a wrong answer. The lazy template gets 2, because it pushes node 1 again when its cost drops and expands it a second time, and node 3 after it.

That self-repair is not a fix. Every extra expansion can set off more of them, and the work can grow exponentially with the number of nodes: Donald B. Johnson showed in 1973 a family of networks on which this kind of search takes O(n · 2ⁿ) steps. The program below builds a similar family of chained gadgets, each with a refund twice as large as the one before, and counts the expansions:

"""Negative edges without a negative cycle: the lazy version stays right, but its work doubles with every gadget.

Gadget i joins a source a_i to the previous source a_(i-1) twice: directly, for 0, and through b_i, for i and then
-(i + 2^i). The direct edge comes out of the heap first, so everything behind a_(i-1) is expanded; then b_i comes out
and lowers a_(i-1) by 2^i, and everything behind it is expanded again. The refunds double from gadget to gadget, so
every improvement of a_i still improves a_(i-1) twice. There is no cycle at all, so no negative cycle.
"""
import heapq
import math


def gadgets(k):
    """Nodes a_0..a_k are 0..k, b_1..b_k are k+1..2k; the search starts at a_k."""
    edges = []
    for i in range(1, k + 1):
        a, a_prev, b = i, i - 1, k + i
        edges += [(a, a_prev, 0), (a, b, i), (b, a_prev, -(i + 2**i))]
    return 2 * k + 1, edges


def lazy_pops(n, edges, s):
    out = [[] for _ in range(n)]
    for u, v, w in edges:
        out[u].append((v, w))
    dist = [math.inf] * n
    dist[s] = 0
    heap, pops = [(0, s)], 0
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        pops += 1
        for v, w in out[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist, pops


def bellman_ford(n, edges, s):
    """Rounds over every edge until nothing changes: at most n - 1 rounds without a negative cycle."""
    dist = [math.inf] * n
    dist[s] = 0
    relaxations = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            relaxations += 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    return dist, relaxations


print(" k  nodes  edges  lazy Dijkstra pops  Bellman-Ford edge checks   cost of a_0")
for k in [1, 2, 4, 8, 12, 16, 20]:
    n, edges = gadgets(k)
    dist, pops = lazy_pops(n, edges, k)
    bf, relax = bellman_ford(n, edges, k)
    assert dist == bf
    print(f"{k:2}  {n:5}  {len(edges):5}  {pops:18,}  {relax:24,}  {dist[0]:>12,}")

 k  nodes  edges  lazy Dijkstra pops  Bellman-Ford edge checks   cost of a_0
 1      3      3                   4                         6            -2
 2      5      6                  10                        18            -6
 4      9     12                  46                        60           -30
 8     17     24                 766                       216          -510
12     25     36              12,286                       468        -8,190
16     33     48             196,606                       816      -131,070
20     41     60           3,145,726                     1,260    -2,097,150

Every gadget adds 2 nodes and 3 edges and doubles the work: 3 · 2ᵏ − 2 expansions for k gadgets, 3,145,726 on a network of 41 nodes and 60 edges. The network has no cycle at all, so the answers are still right, but twenty more gadgets, 40 more nodes, would multiply the work by about a million. Bellman–Ford, which relaxes every edge in rounds until nothing changes, needs 1,260 edge checks on the same network. When costs can be negative, use Bellman–Ford. It also finds a cycle whose total cost is negative, on which the lazy template would never stop, because every lap lowers the costs again.

A problem solved in full: the cheapest delivery route

The lesson’s network has nine depots and thirteen roads, drawn in the diagram further down. Four examples:

1. From depot 0 to depot 7: a toll of 13, through depots 2, 1, 3, 4 and 5. The routes with the fewest roads, four of them, cost at least 14.
2. From depot 3 to depot 7: 5, through depots 4 and 5.
3. From depot 8 to depot 6: 6, through depots 3 and 4.
4. From depot 7 to depot 0: −1. Every road is one-way, and none leaves depot 7.

The brute force: try every route

Walk every route from s that never visits a depot twice, depth first, and keep the cheapest one that reaches t. Nobody doubts its answers, so it is the reference that faster code gets tested against. The program lists the routes from depot 0 to depot 7, then counts the routes on complete networks, where every depot has a road to every other:

"""The cheapest toll found by trying every route: always right, and hopeless beyond a dozen depots."""
import math

ROADS = [
    (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2),
    (3, 5, 6), (4, 5, 1), (4, 6, 3), (5, 7, 2), (6, 7, 4), (8, 3, 1),
]


def every_route(n, roads, s, t):
    """Yields (toll, route) for every route from s to t that visits no depot twice, depth first."""
    out = [[] for _ in range(n)]
    for u, v, toll in roads:
        out[u].append((v, toll))
    route, on_route = [s], [False] * n
    on_route[s] = True

    def extend(u, paid):
        if u == t:
            yield paid, list(route)
            return
        for v, toll in out[u]:
            if not on_route[v]:
                on_route[v] = True
                route.append(v)
                yield from extend(v, paid + toll)
                route.pop()
                on_route[v] = False

    yield from extend(s, 0)


routes = sorted(every_route(9, ROADS, 0, 7))
print(f"routes from 0 to 7: {len(routes)}")
for toll, route in routes:
    print(f"  toll {toll:2}, {len(route) - 1} roads: {' '.join(map(str, route))}")

# On a complete network, where every depot has a road to every other, the routes multiply.
print("depots  routes from 0 to the last depot")
for n in range(3, 9):
    roads = [(u, v, 1) for u in range(n) for v in range(n) if u != v]
    counted = sum(1 for _ in every_route(n, roads, 0, n - 1))
    formula = sum(math.perm(n - 2, k) for k in range(n - 1))  # k depots in between, in order
    assert counted == formula
    print(f"{n:6}  {counted:,}")
for n in [10, 12, 15, 20]:
    print(f"{n:6}  {sum(math.perm(n - 2, k) for k in range(n - 1)):,} (from the formula)")

routes from 0 to 7: 11
  toll 13, 6 roads: 0 2 1 3 4 5 7
  toll 14, 5 roads: 0 1 3 4 5 7
  toll 14, 5 roads: 0 2 3 4 5 7
  toll 14, 4 roads: 0 2 4 5 7
  toll 16, 5 roads: 0 2 1 3 5 7
  toll 17, 4 roads: 0 1 3 5 7
  toll 17, 6 roads: 0 2 1 3 4 6 7
  toll 17, 4 roads: 0 2 3 5 7
  toll 18, 5 roads: 0 1 3 4 6 7
  toll 18, 5 roads: 0 2 3 4 6 7
  toll 18, 4 roads: 0 2 4 6 7
depots  routes from 0 to the last depot
     3  2
     4  5
     5  16
     6  65
     7  326
     8  1,957
    10  109,601 (from the formula)
    12  9,864,101 (from the formula)
    15  16,926,797,486 (from the formula)
    20  17,403,456,103,284,421 (from the formula)

The nine depots have 11 routes from 0 to 7, and the cheapest is one of the longest, with six roads. On complete networks the count explodes, because a route may visit the other depots in any order: 1,957 routes between two of 8 depots, 9,864,101 between two of 12, and about 1.7 × 10¹⁶ between two of 20. At 100,000 depots the brute force is hopeless.

What to notice

The cheapest route to depot 7 passes depot 5, and its part from depot 0 to depot 5 is itself a cheapest route to depot 5: if a cheaper one existed, the route to 7 could use it and get cheaper too. So cheapest routes are built from cheapest routes, and if depots were settled in increasing order of cost, each one’s cost could be worked out from depots already settled. That order is what a heap provides. And every toll is at least 0, so no route gets cheaper as it grows, which is the condition the method needs.

Dijkstra’s algorithm, step by step

1. Build out[u], the list of (v, toll) pairs for the roads leaving depot u.
2. Set dist[s] = 0, every other dist to infinity and every parent to −1, and put (0, s) in a min-heap.
3. Take out the cheapest entry (d, u). If d > dist[u], it is stale: skip it.
4. If u is t, stop: its toll is final.
5. For every road (v, toll) in out[u] with d + toll < dist[v], set dist[v] = d + toll and parent[v] = u, and push (dist[v], v).
6. Repeat from step 3 while the heap is not empty.
7. If dist[t] is still infinity, return −1 and an empty route. Otherwise follow parent from t back to s, reverse the list, and return it with dist[t].

Step 4 lets the search stop early: once the target leaves the heap, nothing found later can make it cheaper. Without that step the same loop computes the cheapest toll to every depot, which is what the exercise below asks for.

Why it is correct

Call a depot settled once an entry with its current cost has come out of the heap. Two facts hold throughout the run.

1. dist[v] is always the toll of a real route from s to v, or infinity. It is only ever set to d + toll for a road out of a depot that was reached for d, so it is never less than the cheapest toll.
2. Every settled depot has its cheapest toll. Suppose not, and let u be the first depot settled with a cost d larger than its cheapest toll c. Take a cheapest route R to u, let y be the first depot on R that is not settled yet, and x the depot just before it, which is settled. The start s was settled first, at cost 0, so x exists. When x was settled, its cost was right, because u is the first exception, and the road from x to y was relaxed, so dist[y] is at most the toll of R up to y. The rest of R, from y to u, costs at least 0, because no toll is negative, so dist[y] ≤ c < d. The last time dist[y] dropped, an entry with that cost went into the heap, and it is still there, because y is not settled. That entry is cheaper than d, so it would have come out before (d, u): a contradiction. If y is u itself, the same inequality says dist[u] < d, so (d, u) was stale and could not have settled u.

So a depot’s toll is final when it is settled, which justifies both step 4 and the stale check: a later entry of a settled depot can never carry a lower cost. Each parent[v] is set together with dist[v] and names a depot settled earlier, so the walk back from t passes depots in reverse order of settling, pays exactly dist[t] and ends at s. Strike out “because no toll is negative” and the proof falls apart, which is what the refund example showed.

A dry run

The search from depot 0 to depot 7, one row for every entry taken out of the heap:

The parents recorded on the way are 2 for depot 1, 0 for depot 2, 1 for depot 3, 3 for depot 4, 4 for depots 5 and 6, and 5 for depot 7. Walking them back from depot 7 gives 5, 4, 3, 1, 2 and 0, so the route is 0, 2, 1, 3, 4, 5, 7. Eleven entries came out of the heap and four of them were stale; the twelfth, (14, 5), was still waiting when the search stopped.

The code in five languages

"""The cheapest toll from one depot to another, and one route with it: Dijkstra's algorithm with a heap."""
import heapq
import math

# The courier network of the lesson: one-way roads (from, to, toll).
ROADS = [
    (0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2),
    (3, 5, 6), (4, 5, 1), (4, 6, 3), (5, 7, 2), (6, 7, 4), (8, 3, 1),
]


def cheapest_route(n, roads, s, t):
    """(toll, route): the cheapest total toll from s to t and one route that pays it, or (-1, [])."""
    out = [[] for _ in range(n)]
    for u, v, toll in roads:
        out[u].append((v, toll))
    dist = [math.inf] * n
    parent = [-1] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale: u was reached more cheaply after this entry was pushed
        if u == t:
            break  # t has left the heap, so its toll is final
        for v, toll in out[u]:
            if d + toll < dist[v]:
                dist[v] = d + toll
                parent[v] = u
                heapq.heappush(heap, (dist[v], v))
    if dist[t] == math.inf:
        return -1, []
    route = [t]
    while route[-1] != s:
        route.append(parent[route[-1]])
    route.reverse()
    return dist[t], route


for s, t in [(0, 7), (3, 7), (8, 6), (7, 0)]:
    toll, route = cheapest_route(9, ROADS, s, t)
    print(f"{s} to {t}: {toll}" + (" via " + " ".join(map(str, route)) if route else ""))

0 to 7: 13 via 0 2 1 3 4 5 7
3 to 7: 5 via 3 4 5 7
8 to 6: 6 via 8 3 4 6
7 to 0: -1

// The cheapest toll from one depot to another, and one route with it: Dijkstra's algorithm with a heap.
// JavaScript has no built-in heap, so a small binary min-heap of [toll, depot] pairs comes first.

class MinHeap {
  constructor() {
    this.a = [];
  }
  get size() {
    return this.a.length;
  }
  static less(x, y) {
    return x[0] < y[0] || (x[0] === y[0] && x[1] < y[1]);
  }
  push(item) {
    const a = this.a;
    a.push(item);
    for (let i = a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (!MinHeap.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && MinHeap.less(a[l], a[m])) m = l;
        if (r < a.length && MinHeap.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

// The courier network of the lesson: one-way roads [from, to, toll].
const ROADS = [
  [0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2],
  [3, 5, 6], [4, 5, 1], [4, 6, 3], [5, 7, 2], [6, 7, 4], [8, 3, 1],
];

function cheapestRoute(n, roads, s, t) {
  const out = Array.from({ length: n }, () => []);
  for (const [u, v, toll] of roads) out[u].push([v, toll]);
  const dist = new Array(n).fill(Infinity);
  const parent = new Array(n).fill(-1);
  dist[s] = 0;
  const heap = new MinHeap();
  heap.push([0, s]);
  while (heap.size > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue; // stale entry
    if (u === t) break; // t has left the heap: its toll is final
    for (const [v, toll] of out[u]) {
      if (d + toll < dist[v]) {
        dist[v] = d + toll;
        parent[v] = u;
        heap.push([dist[v], v]);
      }
    }
  }
  if (dist[t] === Infinity) return { toll: -1, route: [] };
  const route = [t];
  while (route[route.length - 1] !== s) route.push(parent[route[route.length - 1]]);
  route.reverse();
  return { toll: dist[t], route };
}

for (const [s, t] of [[0, 7], [3, 7], [8, 6], [7, 0]]) {
  const { toll, route } = cheapestRoute(9, ROADS, s, t);
  console.log(`${s} to ${t}: ${toll}` + (route.length ? ` via ${route.join(" ")}` : ""));
}

0 to 7: 13 via 0 2 1 3 4 5 7
3 to 7: 5 via 3 4 5 7
8 to 6: 6 via 8 3 4 6
7 to 0: -1

// The cheapest toll from one depot to another, and one route with it: Dijkstra's algorithm with a heap.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class CheapestRoute {
    record Result(long toll, List<Integer> route) {}

    // The courier network of the lesson: one-way roads {from, to, toll}.
    static final int[][] ROADS = {
        {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2},
        {3, 5, 6}, {4, 5, 1}, {4, 6, 3}, {5, 7, 2}, {6, 7, 4}, {8, 3, 1},
    };

    static Result cheapestRoute(int n, int[][] roads, int s, int t) {
        List<List<int[]>> out = new ArrayList<>();
        for (int i = 0; i < n; i++) out.add(new ArrayList<>());
        for (int[] r : roads) out.get(r[0]).add(new int[] {r[1], r[2]});
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        dist[s] = 0;
        // Entries {toll, depot}, cheapest first; long because a route's toll can pass 2^31 on large inputs.
        PriorityQueue<long[]> heap = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
        heap.add(new long[] {0, s});
        while (!heap.isEmpty()) {
            long[] top = heap.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue; // stale entry
            if (u == t) break; // t has left the heap: its toll is final
            for (int[] e : out.get(u)) {
                int v = e[0];
                if (d + e[1] < dist[v]) {
                    dist[v] = d + e[1];
                    parent[v] = u;
                    heap.add(new long[] {dist[v], v});
                }
            }
        }
        if (dist[t] == Long.MAX_VALUE) return new Result(-1, List.of());
        List<Integer> route = new ArrayList<>();
        route.add(t);
        while (route.get(route.size() - 1) != s) route.add(parent[route.get(route.size() - 1)]);
        Collections.reverse(route);
        return new Result(dist[t], route);
    }

    public static void main(String[] args) {
        int[][] queries = {{0, 7}, {3, 7}, {8, 6}, {7, 0}};
        for (int[] q : queries) {
            Result r = cheapestRoute(9, ROADS, q[0], q[1]);
            StringBuilder line = new StringBuilder(q[0] + " to " + q[1] + ": " + r.toll());
            if (!r.route().isEmpty()) {
                line.append(" via");
                for (int v : r.route()) line.append(' ').append(v);
            }
            System.out.println(line);
        }
    }
}

// The cheapest toll from one depot to another, and one route with it: Dijkstra's algorithm with a heap.
#include <algorithm>
#include <cstdio>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

struct Road {
    int from, to, toll;
};

// The courier network of the lesson: one-way roads.
const std::vector<Road> ROADS = {
    {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2},
    {3, 5, 6}, {4, 5, 1}, {4, 6, 3}, {5, 7, 2}, {6, 7, 4}, {8, 3, 1},
};

// Returns the cheapest toll from s to t (-1 if t cannot be reached) and fills route with one cheapest route.
long long cheapest_route(int n, const std::vector<Road>& roads, int s, int t, std::vector<int>& route) {
    std::vector<std::vector<std::pair<int, int>>> out(n);
    for (const Road& r : roads) out[r.from].push_back({r.to, r.toll});
    const long long INF = std::numeric_limits<long long>::max();
    std::vector<long long> dist(n, INF);
    std::vector<int> parent(n, -1);
    dist[s] = 0;
    // A min-heap of (toll, depot): std::priority_queue is a max-heap unless it is given std::greater.
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<>> heap;
    heap.push({0, s});
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (d > dist[u]) continue;  // stale entry
        if (u == t) break;          // t has left the heap: its toll is final
        for (auto [v, toll] : out[u]) {
            if (d + toll < dist[v]) {
                dist[v] = d + toll;
                parent[v] = u;
                heap.push({dist[v], v});
            }
        }
    }
    route.clear();
    if (dist[t] == INF) return -1;
    for (int v = t;; v = parent[v]) {
        route.push_back(v);
        if (v == s) break;
    }
    std::reverse(route.begin(), route.end());
    return dist[t];
}

int main() {
    const std::pair<int, int> queries[] = {{0, 7}, {3, 7}, {8, 6}, {7, 0}};
    for (auto [s, t] : queries) {
        std::vector<int> route;
        long long toll = cheapest_route(9, ROADS, s, t, route);
        std::printf("%d to %d: %lld", s, t, toll);
        if (!route.empty()) {
            std::printf(" via");
            for (int v : route) std::printf(" %d", v);
        }
        std::printf("\n");
    }
}

// The cheapest toll from one depot to another, and one route with it: Dijkstra's algorithm with a heap.
package main

import (
	"container/heap"
	"fmt"
	"math"
	"slices"
	"strings"
)

// entry is one heap item: a depot and the toll it was reached for.
type entry struct {
	toll  int64
	depot int
}

// tollHeap satisfies heap.Interface; Less puts the cheapest entry first.
type tollHeap []entry

func (h tollHeap) Len() int           { return len(h) }
func (h tollHeap) Less(i, j int) bool { return h[i].toll < h[j].toll }
func (h tollHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *tollHeap) Push(x any)        { *h = append(*h, x.(entry)) }
func (h *tollHeap) Pop() any {
	old := *h
	last := old[len(old)-1]
	*h = old[:len(old)-1]
	return last
}

// The courier network of the lesson: one-way roads {from, to, toll}.
var roads = [][3]int{
	{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5}, {2, 3, 8}, {2, 4, 10}, {3, 4, 2},
	{3, 5, 6}, {4, 5, 1}, {4, 6, 3}, {5, 7, 2}, {6, 7, 4}, {8, 3, 1},
}

// cheapestRoute returns the cheapest toll from s to t and one route with it, or -1 and nil.
func cheapestRoute(n int, roads [][3]int, s, t int) (int64, []int) {
	out := make([][][2]int, n)
	for _, r := range roads {
		out[r[0]] = append(out[r[0]], [2]int{r[1], r[2]})
	}
	dist := make([]int64, n)
	parent := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt64
		parent[i] = -1
	}
	dist[s] = 0
	h := &tollHeap{{0, s}}
	for h.Len() > 0 {
		top := heap.Pop(h).(entry)
		d, u := top.toll, top.depot
		if d > dist[u] {
			continue // stale entry
		}
		if u == t {
			break // t has left the heap: its toll is final
		}
		for _, e := range out[u] {
			v, toll := e[0], int64(e[1])
			if d+toll < dist[v] {
				dist[v] = d + toll
				parent[v] = u
				heap.Push(h, entry{dist[v], v})
			}
		}
	}
	if dist[t] == math.MaxInt64 {
		return -1, nil
	}
	route := []int{t}
	for route[len(route)-1] != s {
		route = append(route, parent[route[len(route)-1]])
	}
	slices.Reverse(route)
	return dist[t], route
}

func main() {
	for _, q := range [][2]int{{0, 7}, {3, 7}, {8, 6}, {7, 0}} {
		toll, route := cheapestRoute(9, roads, q[0], q[1])
		line := fmt.Sprintf("%d to %d: %d", q[0], q[1], toll)
		if len(route) > 0 {
			parts := make([]string, len(route))
			for i, v := range route {
				parts[i] = fmt.Sprint(v)
			}
			line += " via " + strings.Join(parts, " ")
		}
		fmt.Println(line)
	}
}

from session import run, versions

# CheapestRoute.java runs as a single source file, cheapest_route.cpp is built with the sanitizers on, and the Go
# program runs with go run.
versions("java -version", "clang++ --version", "go version")
run("""
java CheapestRoute.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined cheapest_route.cpp -o cheapest_route && ./cheapest_route
go run cheapest_route.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java CheapestRoute.java
0 to 7: 13 via 0 2 1 3 4 5 7
3 to 7: 5 via 3 4 5 7
8 to 6: 6 via 8 3 4 6
7 to 0: -1
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined cheapest_route.cpp -o cheapest_route && ./cheapest_route
0 to 7: 13 via 0 2 1 3 4 5 7
3 to 7: 5 via 3 4 5 7
8 to 6: 6 via 8 3 4 6
7 to 0: -1
$ go run cheapest_route.go
0 to 7: 13 via 0 2 1 3 4 5 7
3 to 7: 5 via 3 4 5 7
8 to 6: 6 via 8 3 4 6
7 to 0: -1

All five print the same four lines. Where they differ:

• Python pushes (toll, depot) tuples with heapq; when two tolls tie, the depot numbers decide, which is harmless.
• JavaScript has no heap in its standard library, so the file starts with a binary heap of [toll, depot] pairs. Its numbers are exact integers up to 2⁵³ − 1, far above any toll here.
• Java keeps long[] pairs in a PriorityQueue with a comparator on the toll. Its documentation gives O(log n) for add and poll but linear time for remove(Object), one more reason to leave stale entries where they are. A cheapest route uses at most 99,999 roads of at most 10,000 each, below 2³¹, but long keeps the code safe for larger tolls.
• C++ turns std::priority_queue, a max-heap by default, into a min-heap with std::greater<>. The build runs AddressSanitizer and UndefinedBehaviorSanitizer, which found nothing.
• Go implements the five methods of heap.Interface. The package’s heap.Fix can lower an entry’s cost in place in O(log n), but only if the code tracks where each depot sits in the slice, bookkeeping that lazy deletion avoids.

Checked against the brute force

"""Dijkstra's answer checked against every route, on 3,000 random networks with repeated roads and zero tolls."""
import heapq
import math
import random


def cheapest_route(n, roads, s, t):
    out = [[] for _ in range(n)]
    for u, v, toll in roads:
        out[u].append((v, toll))
    dist, parent = [math.inf] * n, [-1] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        if u == t:
            break
        for v, toll in out[u]:
            if d + toll < dist[v]:
                dist[v], parent[v] = d + toll, u
                heapq.heappush(heap, (dist[v], v))
    if dist[t] == math.inf:
        return -1, []
    route = [t]
    while route[-1] != s:
        route.append(parent[route[-1]])
    return dist[t], route[::-1]


def every_toll(n, roads, s, t):
    """The toll of every route from s to t that repeats no depot (parallel roads give separate routes)."""
    out = [[] for _ in range(n)]
    for u, v, toll in roads:
        out[u].append((v, toll))
    seen, tolls = {s}, []

    def extend(u, paid):
        if u == t:
            tolls.append(paid)
            return
        for v, toll in out[u]:
            if v not in seen:
                seen.add(v)
                extend(v, paid + toll)
                seen.remove(v)

    extend(s, 0)
    return tolls


rng = random.Random(59)
unreachable = tied = zero_used = 0
for _ in range(3000):
    n = rng.randint(2, 7)
    roads = [(rng.randrange(n), rng.randrange(n), rng.randint(0, 9)) for _ in range(rng.randint(2, 16))]
    s, t = rng.randrange(n), rng.randrange(n)
    toll, route = cheapest_route(n, roads, s, t)
    tolls = every_toll(n, roads, s, t)
    assert toll == (min(tolls) if tolls else -1), (n, roads, s, t)
    if not tolls:
        unreachable += 1
        continue
    tied += tolls.count(toll) > 1
    # The route must start at s, end at t and pay exactly the toll, using the cheapest road of each step.
    assert route[0] == s and route[-1] == t
    steps = [min(w for u, v, w in roads if (u, v) == (a, b)) for a, b in zip(route, route[1:])]
    assert sum(steps) == toll
    zero_used += 0 in steps
print(f"3,000 networks agree: {unreachable:,} with no route, {tied:,} with tied cheapest routes, "
      f"{zero_used:,} whose route uses a zero-toll road")

3,000 networks agree: 948 with no route, 105 with tied cheapest routes, 267 whose route uses a zero-toll road

The networks have 2 to 7 depots and up to 16 roads, chosen at random with repeats, so the awkward cases turn up often: 948 networks have no route from the start to the target, 105 have several cheapest routes, and in 267 the route returned uses a road with a toll of 0. In every one the toll equals the cheapest of all routes, and the route starts at the start, ends at the target and pays exactly that toll.

The cost

At the limits, 100,000 depots and 200,000 roads, the heap version does at most 200,001 pushes and as many pops, each through at most 18 levels: about 7 million steps. The array scan would look at 10¹⁰ entries.

Variants of the template

• Two-way roads. Add each road to the lists of both of its ends: a two-way road is two one-way roads with the same toll.
• Several starting points. Put every start in the heap at cost 0. The result is the cost from the nearest start, as if one extra node had roads costing 0 to all of them.
• Costs on nodes. An entry fee at a depot can be added to the toll of every road into it, so that only edges carry costs.
• The number of cheapest routes. When d + toll equals dist[v], add ways[u] to ways[v]; when it is less, replace ways[v] with ways[u]. This needs every toll to be positive: with tolls of 0, two depots at the same cost can come out in either order, and a count could be read before it is complete.
• A budget. To list every node within a budget B, stop as soon as the entry taken out costs more than B.

The rest of this module changes one thing at a time: the way costs combine along a route, such as the largest single step or a product of probabilities; edges that cost only 0 or 1; a limit on the number of edges; all pairs at once; and extra state carried along, such as fuel or coupons.

Exercise

roads = [(0, 1, 7), (0, 2, 2), (2, 1, 3), (1, 3, 1), (2, 3, 9), (4, 5, 0)]
cheapest_cost(6, roads, 0)   # [0, 5, 2, 6, -1, -1]: town 1 costs 2 + 3 through town 2, not 7
cheapest_cost(6, roads, 4)   # [-1, -1, -1, -1, 0, 0]: the road from 4 to 5 costs nothing
cheapest_cost(1, [], 0)      # [0]

from collections import deque


def cheapest_cost(n, roads, s):
    """The cheapest total toll from town s to every town, with -1 for towns that s cannot reach."""
    # This BFS reaches the right towns, but it counts the roads driven, not the tolls paid.
    out = [[] for _ in range(n)]
    for u, v, toll in roads:
        out[u].append(v)
        out[v].append(u)
    dist = [-1] * n
    dist[s] = 0
    queue = deque([s])
    while queue:
        u = queue.popleft()
        for v in out[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

import random

from costs import cheapest_cost

ROADS = [(0, 1, 7), (0, 2, 2), (2, 1, 3), (1, 3, 1), (2, 3, 9), (4, 5, 0)]


def by_rounds(n, roads, s):
    """A different method for checking: relax every road in both directions until nothing changes."""
    inf = float("inf")
    dist = [inf] * n
    dist[s] = 0
    for _ in range(n):
        changed = False
        for u, v, w in roads:
            for a, b in ((u, v), (v, u)):
                if dist[a] + w < dist[b]:
                    dist[b] = dist[a] + w
                    changed = True
        if not changed:
            break
    return [-1 if d == inf else d for d in dist]


def test_the_examples():
    """the three calls of the prompt"""
    assert cheapest_cost(6, ROADS, 0) == [0, 5, 2, 6, -1, -1]
    assert cheapest_cost(6, ROADS, 4) == [-1, -1, -1, -1, 0, 0]
    assert cheapest_cost(1, [], 0) == [0]


def test_roads_run_both_ways():
    """the same network seen from town 3"""
    assert cheapest_cost(6, ROADS, 3) == [6, 1, 4, 0, -1, -1]


def test_parallel_roads_and_loops():
    """the cheaper of two parallel roads counts, and a road back to the same town changes nothing"""
    assert cheapest_cost(3, [(0, 1, 9), (1, 0, 4), (1, 1, 0), (1, 2, 5), (2, 2, 3)], 0) == [0, 4, 9]


def test_a_cheap_detour_beats_a_short_road():
    """five cheap roads cost less than one dear road"""
    roads = [(0, 5, 100)] + [(i, i + 1, 10) for i in range(5)]
    assert cheapest_cost(6, roads, 0) == [0, 10, 20, 30, 40, 50]


def test_the_list_of_roads_is_left_unchanged():
    """the function reads the roads and changes nothing in them"""
    roads = [(0, 1, 3), (1, 2, 4)]
    cheapest_cost(3, roads, 2)
    assert roads == [(0, 1, 3), (1, 2, 4)]


def test_random_networks():
    """400 small random networks, checked by relaxing every road until nothing changes"""
    rng = random.Random(41)
    for _ in range(400):
        n = rng.randint(1, 8)
        roads = [(rng.randrange(n), rng.randrange(n), rng.randint(0, 20)) for _ in range(rng.randint(0, 14))]
        s = rng.randrange(n)
        assert cheapest_cost(n, roads, s) == by_rounds(n, roads, s), (n, roads, s)


def test_twenty_thousand_towns():
    """a chain of 20,000 towns, 40,000 extra roads that never help and one cheap road between the two ends"""
    n = 20_000
    rng = random.Random(7)
    roads = [(i, i + 1, 2) for i in range(n - 1)] + [(0, n - 1, 1)]
    for _ in range(40_000):
        a, b = rng.randrange(n), rng.randrange(n)
        roads.append((a, b, 2 * abs(a - b) + rng.randint(0, 5)))
    rng.shuffle(roads)
    expected = [min(2 * i, 1 + 2 * (n - 1 - i)) for i in range(n)]
    assert cheapest_cost(n, roads, 0) == expected