Read the network, predict a decision, trace the search and explain why a route was chosen. Dijkstra and A* are named in OCR H446 2.3.1(f); the Basic view also offers introductory graph enrichment.
One page, three work areas
Build on the left, trace the graph in the centre, and investigate the distance table or pseudocode on the right. Focus Mode gives the workspace the whole window; Escape exits it. Panels scroll internally when needed.
Build a network
Add nodes, drag or nudge them into place, and choose Connect then two nodes. Select a connection to change its endpoints, cost or delete it. Use Directed connections for arrows. Converting to undirected keeps the first listed cost for opposite pairs; Undo restores them. Costs are whole numbers 0–99; negative costs and self-connections are not supported. Up to 12 nodes and 30 connections are available.
Read the trace
g is the best distance found so far from the start. Via records its predecessor. Open is the frontier, ordered by priority; closed means processed. Ties use alphabetical order. A candidate replaces a distance only when strictly lower. Step backwards, play slowly, or jump to the result. The destination must be selected before returning its route. Other distances may still be tentative.
A* and comparison
A* uses f = g + h. h estimates remaining cost in the same units as connection costs; moving a node does not recalculate it. Admissible estimates never overestimate the true remaining cost; h(goal) must be zero. Consistency also requires h(u) ≤ cost(u,v) + h(v). This lab reopens a closed node if a better route is found. Invalid estimates are allowed for investigation, with a warning that the returned route may not be cheapest.
Advanced comparison advances one event per algorithm per click, holding a completed pane at its result. Compare node selections (including the destination and any reopened selections), connections inspected and route cost. Event counts are teaching steps, not processor timings or a universal speed claim. With h = 0, A* uses the same priority and tie rule as Dijkstra.
Challenges and saving
18 independent challenges require a prediction before tracing. Next-node and intermediate-distance tasks stop at a checkpoint until checked. Equivalent cheapest routes are accepted. Worked help records a helped completion, while retaining a previous independent best. Files and practice are device-local; they do not award course XP or send classroom data to a server.
Teacher reference answers · all 18 activities
1. The first choicePrediction: The smallest tentative distance. Answer: B.
Compare the open distances. B has cost 2 and C has cost 5.
2. A better distancePrediction: Distance to the current node plus the connection cost. Answer: 3.
A → B costs 2, then B → C costs 1. Compare that total with the old distance 5.
3. Read the routePrediction: Where the best known route arrived from. Answer: A B C D E.
Follow predecessors backwards from E, then reverse their order.
4. The cheapest totalPrediction: Adding the costs of its connections. Answer: 6.
Add the costs along A → B → C → D → E.
5. Reject the shortcutPrediction: Can have a higher cost than a detour. Answer: A B D E.
Try the upper branch through B and D. The drawing is not to scale.
6. Follow the arrowsPrediction: Only in its arrow direction. Answer: 5.
The route A → B → D → E uses only forward arrows.
7. A fair tie-breakPrediction: Alphabetical node order. Answer: B.
B comes before C alphabetically. Other deterministic tie rules can also be valid outside this lab.
8. Two valid answersPrediction: Both have the same minimum cost. Answer: A B D.
Compare A B D and A C D.
9. No routePrediction: There is no reachable route. Answer: no route.
D has no connection to the component containing A. Infinity does not mean zero.
10. Free does not mean missingPrediction: Can still be part of a route. Answer: 3.
A → B adds zero; B → C adds 1; C → D adds 2.
11. Introducing fPrediction: f = g + h. Answer: B.
B: g=2, h=4, f=6. C: g=1, h=7, f=8.
12. Estimates are not travel costsPrediction: g at the destination. Answer: 6.
The upper route uses three connections of cost 2. h guides the search but is not added to the route cost.
13. Count the selectionsPrediction: The node is removed from the open set for investigation. Answer: 7.
Count the Select events, including the destination selection. Compare with the counter.
14. A* takes a focused routePrediction: Can guide the order of investigation. Answer: 4.
Compare the A* and Dijkstra panes. A → B → D → F: count those node selections.
15. Check a safe estimatePrediction: Never overestimates the true remaining cost. Answer: yes.
Compare each h with the exact remaining route cost in the heuristic inspector.
16. The misleading estimatePrediction: Return a route that is not cheapest. Answer: no.
B has h=20, but its actual remaining cost is only 1.
17. Find the route A* missedPrediction: g alone as its priority. Answer: A B C.
A → B → C costs 2, compared with direct A → C costing 5.
18. Repair the estimatePrediction: Equivalent to Dijkstra with the same tie rule. Answer: Set B’s h to 0 or 1, then check again..
Change B’s estimate from 20 to either 0 or 1. The destination estimate must remain zero.
OCR A-level specification · A* heuristic reference