PathLab

Weighted graphs · shortest routes · OCR A-level enrichment

Build a network. Predict the next choice. Trace every decision.

Network builder

5/12 nodes

Node A

Select nodes to inspect them. Drag them to arrange your network.

Trace coloursOpen / frontierCurrent nodeClosed / processedReturned route

Costs come from the labels, not line lengths. Moving a node changes the drawing only; h values stay as entered. Edits restart the trace.

Dijkstra · route investigation

A → E
Dijkstrapriority = g
25142110ASTARTg 0Bg ∞Cg ∞Dg ∞E GOALg ∞
0 selections0 connections checkedCost —
00 / 22

Start at A. Its distance is 0; all other distances are unknown (∞).

Your PathLab field guide

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 choice

Prediction: The smallest tentative distance. Answer: B.

Compare the open distances. B has cost 2 and C has cost 5.

2. A better distance

Prediction: 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 route

Prediction: 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 total

Prediction: Adding the costs of its connections. Answer: 6.

Add the costs along A → B → C → D → E.

5. Reject the shortcut

Prediction: 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 arrows

Prediction: Only in its arrow direction. Answer: 5.

The route A → B → D → E uses only forward arrows.

7. A fair tie-break

Prediction: Alphabetical node order. Answer: B.

B comes before C alphabetically. Other deterministic tie rules can also be valid outside this lab.

8. Two valid answers

Prediction: Both have the same minimum cost. Answer: A B D.

Compare A B D and A C D.

9. No route

Prediction: 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 missing

Prediction: Can still be part of a route. Answer: 3.

A → B adds zero; B → C adds 1; C → D adds 2.

11. Introducing f

Prediction: f = g + h. Answer: B.

B: g=2, h=4, f=6. C: g=1, h=7, f=8.

12. Estimates are not travel costs

Prediction: 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 selections

Prediction: 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 route

Prediction: 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 estimate

Prediction: Never overestimates the true remaining cost. Answer: yes.

Compare each h with the exact remaining route cost in the heuristic inspector.

16. The misleading estimate

Prediction: 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* missed

Prediction: g alone as its priority. Answer: A B C.

A → B → C costs 2, compared with direct A → C costing 5.

18. Repair the estimate

Prediction: 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