Artificial Intelligence: Question 2

Syllabus 18.1

Structured A2 8 marks

A warehouse uses an automated delivery robot that moves between five junctions, A to E, connected by fixed two-way paths. The table below gives the distance, in metres, of each path.

Path	Distance (m)
`A` – `B`	4
`A` – `C`	2
`B` – `C`	1
`B` – `D`	5
`B` – `E`	6
`C` – `D`	8
`C` – `E`	10
`D` – `E`	2

The robot starts at junction A and must reach the packing station at junction E, using Dijkstra's algorithm to find the shortest total distance.

(a) Describe, in the context of this scenario, what the nodes and the edges of a graph represent. [2]

(b) Trace Dijkstra's algorithm starting at A. Show the order in which junctions are settled (given a final, shortest distance from A), and state the shortest distance from A to each junction. [4]

Show worked solution Hide worked solution

Part (a): What the nodes and edges represent

In this graph, each node (vertex) represents one of the five junctions, A to E, that the robot can be at. Each edge represents a direct path connecting two junctions, and is weighted with a value (here, the distance in metres) representing the cost of travelling along that path.

[2 marks]: [1] for correctly describing a node as representing a junction, [1] for correctly describing an edge as representing a weighted (distance-labelled) path between two junctions.

Part (b): Tracing Dijkstra’s algorithm

Dijkstra’s algorithm repeatedly settles the unsettled junction with the smallest tentative distance from A, then checks whether travelling through that newly settled junction gives a shorter route to any of its unsettled neighbours, updating their tentative distance if so.

Step	Junction settled	Distance from `A`	Tentative distances updated
1	`A`	0	`B`: 0 + 4 = 4 (via `A`); `C`: 0 + 2 = 2 (via `A`)
2	`C` (smallest, 2)	2	`B`: 2 + 1 = 3 (via `C`, improves on 4); `D`: 2 + 8 = 10 (via `C`); `E`: 2 + 10 = 12 (via `C`)
3	`B` (smallest, 3)	3	`D`: 3 + 5 = 8 (via `B`, improves on 10); `E`: 3 + 6 = 9 (via `B`, improves on 12)
4	`D` (smallest, 8)	8	`E`: 8 + 2 = 10 (via `D`, not smaller than 9, so no change)
5	`E` (smallest, 9)	9	, all junctions now settled

[4 marks]: [1] for settling A first with distance 0 and correctly finding the initial tentative distances for B (4) and C (2); [1] for settling C next (the smallest tentative distance) and updating B to 3 via C; [1] for settling B next and updating D to 8 and E to 9 via B; [1] for correctly settling D then E last, giving the final shortest distances A = 0, B = 3, C = 2, D = 8, E = 9.

Part (c): Shortest path and total distance

Backtracking from E using the “via” junction recorded when each node was settled:

E was settled via B (distance 9 = 3 + 6).
B was settled via C (distance 3 = 2 + 1).
C was settled via A (distance 2 = 0 + 2).

So the shortest path is A → C → B → E, with total distance:

2 + 1 + 6 = 9 metres.

[2 marks]: [1] for the correct path A–C–B–E, [1] for the correct total distance of 9 m.

Final answers

(a) Nodes = junctions; edges = weighted (distance-labelled) two-way paths between junctions
(b) Settling order and shortest distances from A: A = 0, C = 2, B = 3, D = 8, E = 9
(c) Shortest path A – C – B – E, total distance 9 m

Common mistakes

Believing Dijkstra's algorithm settles junctions in the order they are first reached, rather than always settling the unsettled junction with the smallest current tentative distance (e.g. settling B, with tentative distance 4, before C, with tentative distance 2).
Forgetting to update a junction's tentative distance when a shorter route becomes available through a newly settled junction (e.g. leaving B's tentative distance at 4 via A, instead of updating it to 3 once C is settled and the edge C–B is considered).
Assuming the shortest path is the one using the fewest edges (junctions visited), e.g. choosing A–B–E (distance 4 + 6 = 10) over A–C–B–E (distance 2 + 1 + 6 = 9), rather than the path with the smallest total distance.
Stopping the trace as soon as a first, larger tentative distance for E is calculated (12, via C), instead of continuing to update it until E is actually settled with its final, smallest distance (9, via B).
Assuming every path can only be travelled in one direction, rather than recognising the scenario states these are two-way paths, so an edge can be used from either junction it connects.