Dijkstra's Shortest Path · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.
En anglais

Cheapest routes with weights

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. In Dijkstra with nonnegative weights, which reachable unsettled node is settled next?

    • The one with the largest distance
    • Any node chosen without comparing distances
    • The one with the smallest distance

  2. At the start of Dijkstra, what distance does the start node hold?

    • Infinity
    • 0
    • The largest weight

  3. What does relaxing an edge to an unsettled neighbour mean?

    • Keep the lower of the old and candidate costs
    • Keep the higher of the old and candidate costs
    • Replace the cost with the edge weight

  4. A has settled distance 5. B is unsettled with best-known distance 12. The edge from A to B has weight 4. What distance should B hold after relaxing this edge?

    Answer: ______________

  5. After settling the start, why is the smallest finite unsettled distance safe to settle when all weights are nonnegative?

    • Every unsettled node must be directly joined to the start
    • No later route can have a lower total cost
    • Settling changes all remaining edge weights to zero

  6. An undirected graph has only edges S-A:8, A-T:8, S-B:3, B-C:3, C-T:3. Ordinary BFS from S is guaranteed to find a cheapest route to T.

    Circle one:   True   False

  7. A directed graph has only these edges: S to A (7), S to B (2), B to A (1), A to T (3), B to T (9). Run Dijkstra from S. After settling S, B and A and relaxing each node's outgoing edges, which distance row is correct?

    • S=0, A=3, B=2, T=6
    • S=0, A=7, B=2, T=10
    • S=0, A=3, B=2, T=11

  8. Dijkstra starts at M. The predecessor entries are Z: O, O: N, N: M. What route do they record from M to Z?

    • M, O, N, Z
    • Z, O, N, M
    • M, N, O, Z
LightMySky · lightmysky.comW1-mt_GvUzbY92qL-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Cheapest routes with weights W1-mt_GvUzbY92qL-s1

  1. The one with the smallest distance · Choose the smallest finite best-known distance among unsettled nodes.
  2. 0 · The route from the start to itself costs nothing.
  3. Keep the lower of the old and candidate costs · Add the edge weight to the chosen node's distance, then keep the smaller of that candidate and the neighbour's old distance.
  4. 9 · The route through A costs 5 + 4 = 9. Since 9 is less than 12, replace B's distance with 9.
  5. No later route can have a lower total cost · Any rival route crosses into the unsettled set. Its prefix cannot beat the selected distance, and nonnegative remaining edges cannot lower its cost.
  6. False · BFS finds the two-edge route S-A-T, costing 16. The three-edge route S-B-C-T costs 9, so the BFS route is not cheapest.
  7. S=0, A=3, B=2, T=6 · B lowers A from 7 to 3. A then lowers T from 11 to 6. The resulting distances are S=0, A=3, B=2, T=6.
  8. M, N, O, Z · Follow predecessors from Z to get Z, O, N, M. Reverse that list to recover the route M, N, O, Z.
Worksheet · LightMySky