Home · A-Level Computer Science 9618 · Artificial Intelligence · Graphs in AI: Dijkstra's and A* algorithms · Practice
A2 · Practice questions · Graphs in AI: Dijkstra's and A* algorithms

Trace the route.

Six original Cambridge-style questions on graphs, Dijkstra's algorithm and the A* algorithm, with full traces in the solutions.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.
Keep these straight

Smallest first.

01
Recall
[3 marks]

Describe the structure of a weighted, directed graph.

  • A set of nodes / vertices. ✓
  • Joined by edges / arcs, each with a direction (it can only be travelled one way). ✓
  • Each edge has a weight / cost, such as distance or time. ✓
02
Explain
[3 marks]

Explain how a graph can be used to help an AI system plan the route of a delivery robot through a warehouse.

  • Each location / junction in the warehouse is a node; each aisle the robot can travel along is an edge. ✓
  • Edge weights record the cost of each aisle (distance or travel time); blocked aisles can be removed or given a high weight. ✓
  • A search algorithm such as Dijkstra or A* finds the lowest-cost path from the robot's node to the target node. ✓
03
Trace
[5 marks]

An undirected graph has these edges: P-Q 7, P-R 3, R-Q 2, R-S 8, Q-S 4, Q-T 9, S-T 2.

Use Dijkstra's algorithm starting at P. Give the order in which the nodes are visited, the final shortest distance to each node, and the shortest route from P to T.

  • Visit P (0): Q = 7, R = 3. ✓
  • Visit R (3): Q = 3 + 2 = 5 (replaces 7), S = 3 + 8 = 11. ✓
  • Visit Q (5): S = 5 + 4 = 9 (replaces 11), T = 5 + 9 = 14. ✓
  • Visit S (9): T = 9 + 2 = 11 (replaces 14). Visit T (11). Order P, R, Q, S, T. ✓
  • Distances P 0, R 3, Q 5, S 9, T 11; route P → R → Q → S → T (11). ✓
04
Trace
[6 marks]

An undirected graph has these edges: S-A 2, S-B 5, A-C 6, A-D 3, B-D 2, C-G 2, D-G 6.

The heuristic values are: h(S) = 8, h(A) = 7, h(B) = 6, h(C) = 2, h(D) = 4, h(G) = 0.

Use the A* algorithm to find the shortest route from S to G. Show g, h and f for each node and the order in which nodes are expanded.

  • Expand S (f = 0 + 8 = 8): A g = 2, f = 9; B g = 5, f = 11. ✓
  • Expand A (f = 9): C g = 8, f = 10; D g = 5, f = 9. ✓
  • Expand D (f = 9): G g = 11, f = 11; B via D would be 7, worse than 5, so no change. ✓
  • Expand C (f = 10): G via C is 8 + 2 = 10, better than 11, so G becomes g = 10, f = 10 with previous node C. ✓
  • Expand G (f = 10, the smallest): goal reached. Expansion order S, A, D, C, G. ✓
  • Shortest route S → A → C → G, cost 10. ✓
05
Explain
[3 marks]

Compare Dijkstra's algorithm with the A* algorithm.

  • Dijkstra chooses the next node using only the cost from the start (g); A* uses f = g + h, adding a heuristic estimate of the cost to the goal. ✓
  • A* is directed towards the goal so usually expands fewer nodes / is faster for a single destination. ✓
  • Dijkstra finds the shortest path to every node and needs no heuristic; A* needs a good (admissible) heuristic to guarantee the shortest path. ✓
06
Analysis
[3 marks]

A programmer uses straight-line distance as the heuristic for A* on a road map. A colleague suggests multiplying every heuristic value by 3 so that the search finishes sooner. Discuss this suggestion.

  • Straight-line distance never overestimates road distance, so it is admissible and A* is guaranteed to find the shortest route. ✓
  • Multiplying by 3 can make h larger than the true remaining cost, so the heuristic is no longer admissible. ✓
  • The search may expand fewer nodes and finish sooner, but it may return a route that is not the shortest. ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.