Weighted shortest route
Revise tentative route costs instead of assuming fewer hops means cheaper.
Adult planning suggestion: about9–12 · Logic & rule checking
- Players
- 2–4 per group
- Time
- 15–25 minutes
- Materials
- Node map A–E, seven cost labels and distance table.
Prepare
Use undirected edges AB4,AC1,CB2,BD1,CD5,DE1,CE9. Start A and seek the minimum total cost to E. All costs are nonnegative and are added along a route. Drawn line length has no cost. Assign distance 0 to A and infinity to the others.
Play
Select the unsettled node with smallest tentative distance, breaking ties alphabetically. Mark it settled. For each unsettled neighbour, compare its old distance with current distance plus that edge cost; replace it only if smaller, recording the predecessor. Continue until E is settled. This procedure relies on nonnegative costs.
Worked example
After A, B is 4 and C1. Settle C: B improves to 3, D becomes 6 and E10. Settle B: D improves to 4. Settle D: E improves to 5. Settle E. The route A–C–B–D–E costs 1+2+1+1=5; the shorter-looking A–C–E costs 10.
Finish and check
Read predecessors backward from E to reconstruct the route, then add edge costs again. A spanning tree connecting every node is a different objective: do not add unrelated branches to the courier’s bill. Finish when the route and total are both independently checked.
Adaptation and limits
For thirty learners use ten trios with chooser, calculator and auditor. Allow a table of additions and an adult scribe. A larger diagram is fine, but do not introduce negative edges and continue using the same settled-node guarantee. This is a paper technical task, not a claim of long-term mathematics gains.
Purpose, observation and provenance
Within this activity: Revise tentative route costs instead of assuming fewer hops means cheaper.
Ask why a previously proposed distance may improve and how the predecessor changes.
Our rules, examples and printable diagrams are separately prepared. The earliest inventor of the broader mechanism is not established here.
CP Algorithms — Dijkstra algorithm — Technical nonnegative shortest-path method; our graph and age planning are independent.
Age bands are planning suggestions. Goals describe observable actions, not measured long-term gains or institutional endorsement.
Free alternative: Copy the supplied grids, labels and cards onto reused paper. No specialist product is needed. Adults may prepare pieces or act as a scribe.
Printable materials
Preview at 100% scale, with browser headers and footers off. Cut with suitable help. Keep host keys separate. This is a manual tabletop kit, not an online opponent, automatic judge or solver.
Player materials · Weighted shortest route
Undirected AB4 AC1 CB2 BD1 CD5 DE1 CE9.
Node / tentative distance / predecessor / settled order.
Player record · keep host key separate
| Node | Distance | Parent | Settled |
|---|---|---|---|
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
Host key · separate from players
Settled A,C,B,D,E; distances 0,1,3,4,5. A–C–B–D–E costs 5.
Run the round
Use undirected edges AB4,AC1,CB2,BD1,CD5,DE1,CE9. Start A and seek the minimum total cost to E. All costs are nonnegative and are added along a route. Drawn line length has no cost. Assign distance 0 to A and infinity to the others.
Select the unsettled node with smallest tentative distance, breaking ties alphabetically. Mark it settled. For each unsettled neighbour, compare its old distance with current distance plus that edge cost; replace it only if smaller, recording the predecessor. Continue until E is settled. This procedure relies on nonnegative costs.
After A, B is 4 and C1. Settle C: B improves to 3, D becomes 6 and E10. Settle B: D improves to 4. Settle D: E improves to 5. Settle E. The route A–C–B–D–E costs 1+2+1+1=5; the shorter-looking A–C–E costs 10.
Read predecessors backward from E to reconstruct the route, then add edge costs again. A spanning tree connecting every node is a different objective: do not add unrelated branches to the courier’s bill. Finish when the route and total are both independently checked.
For thirty learners use ten trios with chooser, calculator and auditor. Allow a table of additions and an adult scribe. A larger diagram is fine, but do not introduce negative edges and continue using the same settled-node guarantee. This is a paper technical task, not a claim of long-term mathematics gains.
Related activities
Activity library · Weighted bridge network: rules and printable materials