OCR A-Level Computer Science Algorithms and programming (02), June 2025: Question 5

11 marks · Medium difficulty · Trace Table

Apply Dijkstra's algorithm to find the shortest path between planets in a directed graph, explain visualization, and describe how the A* algorithm uses heuristics.

Practise this question

Question

The question presents a directed graph (Fig. 5) representing routes between planets labeled A through H with weighted edges: A to B (weight 10), B to C (weight 5), B to E (weight 1), C to D (weight 2), D to E (weight 5), D to F (weight 5), F to E (weight 20), F to G (weight 7), and G to H (weight 3). Part (a) asks why the graph is a visualisation of the problem for 2 marks. Part (b) asks to trace Dijkstra's algorithm from start node A to node H, providing an empty trace table with columns 'Node', 'Distance travelled', and 'Previous node', and lines to state the final path and distance for 7 marks. Part (c) asks how an A* algorithm uses heuristics to be efficient for 2 marks.
Question text

5 A program is being written that allows users to travel between different planets in a virtual world.

Spaceships are used to travel between planets and there are only set routes that they use.

Fig. 5 shows a directed graph. The nodes represent the different planets and the edges

represent the routes the spaceships can travel.

The arrows on the edges show which way the spaceships can travel. For example, a spaceship

can travel from planet B to planet C, but not from planet C to planet B.

The value on each edge is the cost in space dollars to travel on that route.

Fig. 5

5 H

B C

5 D

E

G

A

F

(a) Explain why this graph is a visualisation of the problem.

… [2]

(b) A user needs to travel from planet A to planet H. They need to travel the least expensive route.

Show how Dijkstra’s algorithm can be used on the directed graph shown in Fig. 5 to find the

shortest path from start planet A to the end planet H.

You must state the nodes on the final path and the distance of this path. Show your working.

You may use the table to give your answer.

Node Distance travelled Previous node

Final path: …

Distance: …

[7]

(c) The A* algorithm can also be used to find the shortest path in a graph.

Describe how an A* algorithm uses heuristics to be an efficient algorithm.

… [2]

Mark scheme

Show the mark scheme The mark scheme details marks for parts (a), (b), and (c). For (a), 2 marks for points such as graphical representation, using symbols, simplifying the problem, or specific graph mappings. For (b), 7 marks total: 1 mark for final path A B E D F G H, 1 mark for final distance 31, and 5 marks for table entries showing nodes A (dist 0), B (dist 10), C (dist 15), D (dist 16), E (dist 11), F (dist 21), G (dist 28), H (dist 31) with appropriate previous nodes. For (c), 2 marks for explaining heuristics as estimated cost to destination, added to path cost, focusing search on promising nodes without visiting every possibility.

5 (a) 1 mark each to max 2 2 Allow mapping of examples from graph for both

marks e.g.

• It is a graphical representation • edges are used to represent routes

• By using objects/symbols • nodes represent planets

• The problem is simplified • shows relative planet positions

• To make the problem easier to understand • shows costs between connected planets

Do not accept abstraction, unless examples are

abstracted visualizations from the given graph

5 (b) 1 mark for final path A B E D F G H 7 Ignore additional rows and crossed out values.

1 mark for final distance 31

1 mark for each section in table

Candidate may show additional rows such as D, 17

Node Distance Previous Marks from C that are calculated but do not overwrite the

travelled node current shortest path.

A 0 N/A / - /

blank

B 10 A 1

C 15 B

D 16 E

E 11 B

F 21 D

G 28 F

H 31 G

5 (c) 1 mark each to max 2 17 2

• Heuristic is an estimated cost of each distance

• Heuristic is added to distance to identify least

cost next step

• It does not revisit routes already visited

• It does not visit every single possibility…

• ...as it focuses on nodes that are promising

• It ignores some areas to speed up finding a

solution

How to answer it

Directed Graphs, Dijkstra's Algorithm & A* Heuristics

What this question tests

This question assesses your understanding of computational thinking and graph traversal algorithms:

  • Visualisation of a problem: Explaining how visual models simplify reality to make complex systems easier to comprehend.
  • Dijkstra’s Algorithm: Tracing the shortest path through a weighted, directed graph using a formal routing table, recording total accumulated distances, and extracting the final optimal path.
  • A* Pathfinding Algorithm: Defining how heuristics guide the search space to make A* more efficient than Dijkstra by prioritising promising paths.
Part (a) • 2 Marks

Visualisation of the Problem

Explaining why the directed graph represents a visualisation

✅ Acceptable Answers (Any 2)

  • It is a graphical / visual representation of the problem.
  • Uses objects/symbols (e.g. circles and arrows) to model real-world entities.
  • Simplifies the problem / strips away unnecessary complexity to make it easier to understand.
  • Contextual application:
    • Nodes represent planets.
    • Edges represent travel routes.
    • Arrows show allowable directions of travel.
    • Weights show fuel/dollar costs between planets.

❌ Common Errors & Pitfalls

  • Vague abstraction: Simply writing "it is abstraction" scores 0 marks unless you explicitly link it to visual elements from the given graph.
  • Missing the 'visual' aspect: Stating only that "it shows planets" without noting that it represents them graphically using nodes and directed edges.
Mark Scheme Note: Max 2 marks. 1 mark per valid point. Credit is given for identifying generic characteristics of visualisation (simplifying, pictorial) OR explicitly mapping symbols from the diagram (nodes = planets, edges = routes).
Part (b) • 7 Marks

Dijkstra's Algorithm Trace

Determining the least expensive route from planet A to planet H

📐 Step-by-Step Traversal Walkthrough

  1. Start at Planet A: Distance = 0 , Previous = None / - . Visited: {A}. From A, the only outgoing edge is to B (cost 10).
  2. Visit Planet B: Current distance = 10 , Previous = A . Outgoing routes:
    • To C: 10 + 5 = 15 (via B).
    • To E: 10 + 1 = 11 (via B).
  3. Visit Planet E (Lowest unvisited distance = 11): Outgoing route:
    • To D: 11 + 5 = 16 (via E).
  4. Visit Planet C (Current distance = 15): Outgoing route to D:
    • 15 + 2 = 17 via C. Since 17 > 16 (the path via E), we do not overwrite the path to D!
  5. Visit Planet D (Current distance = 16, via E): Outgoing routes:
    • To F: 16 + 5 = 21 (via D).
  6. Visit Planet F (Current distance = 21, via D): Outgoing routes:
    • To E: 21 + 20 = 41 (Already visited with lower distance 11 → ignore).
    • To G: 21 + 7 = 28 (via F).
  7. Visit Planet G (Current distance = 28, via F): Outgoing route:
    • To H: 28 + 3 = 31 (via G).
  8. Destination H reached: Total shortest distance = 31 . Trace back: H ← G ← F ← D ← E ← B ← A.
Node (Planet) Distance Travelled Previous Node Marks Awarded
A 0 N/A / - / blank 1 mark
B 10 A 1 mark
C 15 B 1 mark (both correct)
D 16 E
E 11 B 1 mark (both correct)
F 21 D
G 28 F 1 mark (both correct)
H 31 G
Final Path: A → B → E → D → F → G → H Total Distance: 31 (Space Dollars)

🧠 Exam Technique: Table Working

The examiner explicitly states: "Ignore additional rows and crossed out values. Candidates may show additional rows such as D, 17 from C that are calculated but do not overwrite the current shortest path."

Always show your working! If you initially calculated node D as 17 from C, write it down and update it to 16 when you discover the shorter route via E.

❌ Common Calculation Traps

  • Missing the cheaper detour: Going directly B → C → D costs 5 + 2 = 7 (total 17), whereas detouring B → E → D costs 1 + 5 = 6 (total 16).
  • Directional errors: Overlooking arrowheads (e.g. traveling F → E costs 20, but the arrow points strictly from F to E, not E to F).
  • Forgetting start / end statements: 2 marks are awarded solely for stating:
    • Final Path: A B E D F G H (1 mark)
    • Distance: 31 (1 mark)
Part (c) • 2 Marks

A* Algorithm & Heuristics

How heuristics make A* search more efficient than Dijkstra's

💡 Key Knowledge: The A* Evaluation Function

Dijkstra only uses the known path cost from start to node: g(n) .

A* Algorithm adds an estimated cost from current node to target: h(n) (heuristic).

f(n) = g(n) + h(n)

This allows A* to perform an informed search rather than expanding blindly in all directions.

✅ Mark Scheme Scoring Points (Any 2)

  • Definition: A heuristic is an estimate of the cost/distance from the current node to the destination.
  • Function: The heuristic estimate is added to the actual distance travelled to calculate total priority / identify the least-cost next step.
  • Efficiency: It focuses exploration toward the target and avoids visiting every single possibility / ignores unpromising areas.
  • Constraint: It does not revisit paths already evaluated / stops unnecessary exploration.
Examiner Commentary: High-scoring students clearly explained that the heuristic acts as a directional guide, pruning unpromising branches of the graph and reducing the overall number of nodes visited compared to Dijkstra.

Topics

1.4 Data types, data structures and algorithms · 2.2 Problem solving and programming · 2.3 Algorithms · 1.4.2 Data Structures · 2.2.2 Computational methods · 2.3.1 Algorithms

Question and mark scheme from the OCR A-Level Computer Science examination, Algorithms and programming (02), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.