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

Cheapest routes with weights

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

  1. Each round, which node gets settled?

    • The farthest unsettled node
    • A random unsettled node
    • The nearest unsettled node

  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 a neighbour mean?

    • Keep the smaller of the old and via distances
    • Delete the neighbour from the graph
    • Double every weight on the path

  4. One route costs 50 plus 50. Another costs 10 plus 10 plus 10. What is the cheaper total?

    Answer: ______________

  5. Why can a settled node never be improved later?

    • Settled rows are deleted at once
    • Any rival detour already costs at least as much
    • Weights turn negative after settling

  6. Breadth first search is the wrong tool when edges carry different costs.

    Circle one:   True   False

  7. A student settles the farthest node first to finish sooner. What is wrong?

    • Settling must go nearest first to stay safe
    • Farthest nodes are never reachable
    • Tables are banned from the method

  8. Two hops cost 100 total and three hops cost 30 total. Which route wins?

    • The two hop route, fewer hops always wins
    • Neither, hop counts must match
    • The three hop route, cheaper cost wins
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 nearest unsettled node · Smallest best known distance is safe to fix.
  2. 0 · The route from the start to itself costs nothing.
  3. Keep the smaller of the old and via distances · Relaxing only ever improves or keeps a best distance.
  4. 30 · 100 against 30 leaves 30 the cheaper.
  5. Any rival detour already costs at least as much · Leaving the settled region must pass an unsettled node costing no less.
  6. True · It counts hops, so a cheap long route stays hidden.
  7. Settling must go nearest first to stay safe · Only the nearest unsettled distance is provably final.
  8. The three hop route, cheaper cost wins · Cost decides, not hop count, once weights differ.
Worksheet · LightMySky