The shape of the lesson
By the end of the lesson, learners can
- Why AI uses graphs: Many AI problems are really questions about connections: which places are linked, which game positions can follow each other, which actions lead to the goal.
- Dijkstra's algorithm: Dijkstra's algorithm finds the shortest distance from a start node to every other node in a graph whose weights are not negative.
- A* and the heuristic: Dijkstra spreads out evenly in every direction, so it wastes time on nodes that lead away from the goal.
- Dijkstra: visit the unvisited node with the smallest distance from the start; update neighbours if current + weight is smaller.
- A*: f = g + h; expand the open node with the smallest f; stop when the goal is chosen.
- Record previous nodes: then read the route backwards from the goal.
- Show every update: a full working table earns method marks even if one sum slips.
One picture every idea returns to
A graph is a set of nodes (vertices) joined by edges (arcs). Edges can carry weights (a cost such as distance or time) and can be directed or undirected. AI uses graphs to model states and the moves between them, then searches them. Dijkstra's algorithm always visits the unvisited node with the smallest distance from the start, so it finds the shortest path to every node. A* chooses the node with the smallest f = g + h, where g is the cost so far and h is a heuristic estimate of the cost still to go, so it usually reaches the goal after visiting far fewer nodes.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Find the shortest way.. A sat nav, a game character and a delivery robot all face the same problem: a map of places joined by routes, and a need to find the cheapest way through it. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Why AI uses graphs | Many AI problems are really questions about connections: which places are linked, which game positions can follow each other, which actions lead to the goal. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Dijkstra's algorithm | Dijkstra's algorithm finds the shortest distance from a start node to every other node in a graph whose weights are not negative. Model the worked example Trace on Fig. 1 on the board, one line at a time. Your turn: Using the table above, give the shortest distance from A to D and the route. | Pairs |
| 21 to 30 min | Teach and check: A* and the heuristic | Dijkstra spreads out evenly in every direction, so it wastes time on nodes that lead away from the goal. Model the worked example A* against Dijkstra on the board, one line at a time. Your turn: After S is expanded, Dijkstra would visit E next. Why does A* choose B instead? | Jigsaw |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 23 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in A* and the heuristic, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Jigsaw
Split the content into expert pieces. Expert groups master one piece each, then regroup so every home team has one expert per piece, and each expert teaches their piece to the team.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| The syllabus does not ask you to write code for a graph or a search. | It asks you to explain how graphs help AI and to trace Dijkstra and A* by hand, so practise clear, complete working tables. |
| The edge A to B is the most direct way to B, but it is not the shortest: 4 is beaten by A → C → B = 3. | Always compare and update; never treat a distance as final until you visit that node. |
| Do not stop A* when the goal first appears in the open list. | Stop when the goal is chosen (has the smallest f): a cheaper route to it may still be found before then. |
Graphs in AI: Dijkstra's and A* algorithms: worksheet
6 questions, 23 marks. Written in the style of the papers; no past paper question is reproduced.
Describe the structure of a weighted, directed graph.
Explain how a graph can be used to help an AI system plan the route of a delivery robot through a warehouse.
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.
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.
Compare Dijkstra's algorithm with the A* algorithm.
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.
Answer key and marking notes
- 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.
- 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.
- 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).
- 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.
- 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.
- 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.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
A game level is modelled as a graph. Some corridors can only be walked in one direction because of a one-way door. Which kind of graph models this most accurately?
- AA directed graph
- BAn undirected graph
- CAn unweighted tree
- DA graph with no edges
Dijkstra's algorithm is applied to the graph in the figure, starting at P. P and then R have been visited. What is Q's working distance and previous node now?
- A5, previous node R
- B7, previous node P
- C2, previous node R
- D12, previous node R
Use Dijkstra's algorithm on the graph in the figure to find the shortest time from P to U.
- A13 minutes
- B15 minutes
- C17 minutes
- D12 minutes
During an A* search these nodes are in the open list.
| Node | g | h |
|---|---|---|
| K | 6 | 9 |
| L | 9 | 4 |
| M | 4 | 12 |
| N | 11 | 3 |
- AL
- BM
- CN
- DK
An undirected graph has edges S-A 3, S-B 5, A-C 4, A-D 7, B-D 3, C-G 6 and D-G 2. The heuristic values are h(S) = 9, h(A) = 8, h(B) = 4, h(C) = 5, h(D) = 2, h(G) = 0. A* is used to find a route from S to G. In what order are the nodes expanded?
- AS, B, D, G
- BS, A, B, C, D, G
- CS, A, C, G
- DS, B, D, A, G
An undirected graph has edges S-A 2, S-B 4, A-G 7 and B-G 3. A* is run from S to G with h(S) = 6, h(A) = 3, h(B) = 9 and h(G) = 0. Which statement is correct?
- AA* returns S, A, G with cost 9, because h(B) overestimates
- BA* returns S, B, G with cost 7, the shortest route
- CA* returns S, A, G with cost 9, because h(A) underestimates
- DA* cannot finish because h(B) is larger than h(S)
Quiz key
In a directed graph each edge has a direction, so a one-way door becomes an edge that can only be followed one way. An undirected graph lets every edge be travelled both ways, a tree has no cycles and is not the point here, and a graph with no edges records no connections at all.
Visiting P sets Q to 7 (via P) and R to 3. Visiting R gives 3 + 2 = 5 for Q, which is smaller than 7, so Q becomes 5 with previous node R. 7 forgets the update made from R, 2 is only the weight of the edge R to Q and ignores the distance to R, and 12 is R's distance plus the edge R to S (3 + 9), which is S's new distance, not Q's.
Visit order P (0), R (3), Q (5), S (9), T (10), U (13); the route is P, R, Q, S, T, U = 3 + 2 + 4 + 1 + 3 = 13. 15 is the value U first receives when S is visited (9 + 6), before T improves it. 17 is P, R, T, U or P, Q, S, U, routes that look direct but are longer. 12 is the distance S first gets via R (3 + 9), not a distance to U.
f = g + h gives K 15, L 13, M 16 and N 14, so L has the smallest f and is expanded. M has the smallest g, which is what Dijkstra would use; N has the smallest h, which ignores the cost already paid; K is neither the smallest g, h nor f.
From S: A has f = 3 + 8 = 11 and B has f = 5 + 4 = 9, so B is expanded. From B: D gets g = 8 and f = 10, smaller than A's 11, so D is expanded. From D: G gets g = 10 and f = 10, still smaller than 11, so G is chosen and the search stops with route S, B, D, G of cost 10. S, A, B, C, D, G is the order Dijkstra's algorithm would visit using g alone. S, A, C, G follows the smallest single edges and costs 13. Expanding A after D ignores that G already has a smaller f than A.
After S, f(A) = 2 + 3 = 5 and f(B) = 4 + 9 = 13. A is expanded and gives G with f = 9 + 0 = 9, which is smaller than 13, so G is chosen: route S, A, G, cost 9. The true shortest route is S, B, G = 7, missed because h(B) = 9 is more than B's true remaining cost of 3, so the heuristic is not admissible. Underestimating (h(A) = 3 against a true 7) is allowed and does not cause the error, and A* still finishes: a large h only makes a node look worse.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.