Predict the output
What does this print?
import heapq
roads = {0: [(1, 4), (2, 1)], 2: [(1, 2)], 1: []}
best = {0: 0}
heap = [(0, 0)]
order = []
while heap:
t, d = heapq.heappop(heap)
if t > best[d]:
continue
order.append(d)
for nxt, w in roads[d]:
if t + w < best.get(nxt, 10 ** 9):
best[nxt] = t + w
heapq.heappush(heap, (t + w, nxt))
print(order, best[1])Choose an answer, then open Show answer below to check it.
Show answer
Answer: A [0, 2, 1] 3
Right: going via depot 2 (1 + 2) beats the direct road of 4.
The heap pops depots in order of time, and the stale entry (4, 1) is skipped because 3 is already better.
Why not the others?
- B [0, 1, 2] 4. Depot 2 at time 1 is popped before depot 1 at time 4.
- C [0, 2, 1] 4. The route through depot 2 lowers depot 1 to 3.
Steps come from running the Python solution.
Text version
From depot 0:
Nodes [0, 1, 2, 3, 4]; edges 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3).
- Visit 0, distances [0, 4, 1, ∞, ∞]. Settle 0 at 0; improve 1, 2
- Visit 2, distances [0, 3, 1, 6, ∞]. Settle 2 at 1; improve 1, 3
- Visit 1, distances [0, 3, 1, 4, ∞]. Settle 1 at 3; improve 3
- Visit 3, distances [0, 3, 1, 4, 7]. Settle 3 at 4; improve 4
- Visit 4, distances [0, 3, 1, 4, 7]. Settle 4 at 7
Result: [0, 3, 1, 4, 7] (-1 = no route)
From depot 2:
Nodes [0, 1, 2, 3, 4]; edges 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3).
- Visit 2, distances [∞, 2, 0, 5, ∞]. Settle 2 at 0; improve 1, 3
- Visit 1, distances [∞, 2, 0, 3, ∞]. Settle 1 at 2; improve 3
- Visit 3, distances [∞, 2, 0, 3, 6]. Settle 3 at 3; improve 4
- Visit 4, distances [∞, 2, 0, 3, 6]. Settle 4 at 6
Result: [-1, 2, 0, 3, 6] (-1 = no route)