Space: Supermarket networks
View Sequence overviewAlgorithms can be tested and improved by looking for cases where they do not work, then refining the method to make it more reliable.
A shortest-path algorithm provides a repeatable process for comparing total distances and justifying the path with the smallest total weight.
Whole class
Supermarket networks Slides
Each student
Completed Supermarket shortest path Student sheet from previous lesson
Supermarket road networks Student sheet
Task
Show Slide 26. Remind students that in the previous lesson, the greedy algorithm seemed useful because it was simple, quick and worked on the first carpark network. However, the counterexample showed that choosing the shortest next edge does not always give the shortest path overall.
Ask: What caused the greedy algorithm to fail?
Draw out that the finding from the previous lesson that the greedy algorithm only considered the next edge, not the total distance from the starting point.
Explain that this lesson focuses on refining the method so it becomes more reliable and can be applied to new weighted networks.
Pose the challenge: How could the method be improved so that it compares total distances, not just the next edge?
Ask: What could be changed or added to the greedy algorithm to make it more reliable?
Give students time in pairs or small groups to propose improvements and test their ideas on the greedy-failure carpark network from the previous lesson.
Students should consider:
- what information the greedy algorithm used.
- what information it ignored.
- how total distance from the starting vertex could be recorded.
- how different ways of reaching the same vertex could be compared.
- what should happen if a shorter route to a vertex is found.
- what information would be needed to justify the final shortest path.
Students record possible improvements to the algorithm on their Supermarket shortest path Student sheet from the previous lesson.
As students work, circulate and ask:
- Where did the greedy algorithm choose the shortest available edge but miss a better overall route?
- What information did the algorithm have at that moment?
- What information did the algorithm not check?
- How could the algorithm keep track of total distance travelled so far?
- If two routes reach the same vertex, which one should be kept?
- How could the algorithm show that the final path is actually shortest?
Bring the class together after students have written possible improvements to the greedy algorithm.
Explain that the goal is not to create a perfect formal algorithm straight away. The goal is to use what failed in the greedy algorithm to build a more reliable method, then test whether that method works on a new network.
Keep Slide 26 visible and create three columns on the board:
| What the greedy algorithm did | What went wrong | Suggested improvement |
|---|---|---|
Use prompts to help students connect the failure to possible improvements:
- What information did the greedy algorithm look at when making each choice?
- What information did it not look at?
- Where did the total distance from the start become important?
- If two different routes reach the same vertex, which one should be kept?
- What should happen if a shorter route to a vertex is found later?
- What information would need to be recorded so the final path can be justified?
Students may suggest improvements such as:
- recording the total distance travelled so far, not just the next edge.
- writing down the shortest known distance to each vertex.
- comparing different ways of reaching the same vertex.
- keeping the shorter total if two routes reach the same vertex.
- updating the recorded distance if a shorter route is found later.
- keeping track of where each shortest distance came from so the final path can be traced back.
- stopping only when the destination has been reached with the smallest confirmed total.
A possible class version of the refined method might be:
- Write 0 beside the starting vertex and circle the 0 to show that this total is confirmed.
- From that vertex, follow each edge to a neighbouring vertex. Add the edge distance to the circled total and write the resulting total beside the neighbouring vertex.
- Look across the whole network for the smallest total that has not yet been circled. Circle it to show that this total is now confirmed.
- From the vertex beside this newly circled total, follow each edge to a neighbouring vertex. Add the edge distance to the circled total to calculate a new possible total for that neighbour.
- If the neighbouring vertex has no total, write the new total. If it already has a total, keep the smaller total and cross out the larger one.
- Again, look across the whole network for the smallest uncircled total. Circle it and repeat Steps 4–5 from that vertex.
- Continue until the total beside the destination vertex is circled. This confirms the shortest possible distance to the destination from the starting vertex.
- Trace the shortest path backwards from the destination vertex. At each vertex on the way back, choose the connected vertex whose confirmed total, plus the edge between them, gives the current total. Continue until you reach the starting vertex.
Explain that this refined method should be better in theory, but it still needs to be tested. Before applying it to a new network, test it on the counterexample from Slide 26, where the greedy algorithm failed. The aim is to check whether the improved method can reproduce and justify the shortest path in a clear, repeatable way.
Once the refined method has worked on the network where the greedy algorithm failed, explain that this is stronger evidence, but still not the end of the testing process. The next step is to apply the method to a new weighted network and see whether it remains clear, reliable and useful.
Dijkstra’s algorithm
Shortest-path problems can often be solved informally on small networks, but larger networks need a more systematic method. Dijkstra’s algorithm finds the shortest path through a weighted network by comparing the total distance from the starting point, rather than simply choosing the shortest next edge.
The algorithm records the shortest known distance to each vertex and revises these values whenever a shorter route is found. Once a vertex has the smallest unconfirmed total, that distance can be confirmed. This is the key idea behind the refined method students develop in this lesson. Slide 31 provides an animated walkthrough of the algorithm applied to the carpark network.
The algorithm is named after Edsger Dijkstra, a Dutch mathematician and computer scientist who developed it in the 1950s while thinking about how a computer could find the shortest route between locations. His work became foundational in computer science, and shortest-path algorithms based on these ideas are now used in applications such as navigation and network routing. If students ask who Dijkstra was, it is enough to explain that he was one of the pioneers of computer science and that this algorithm is named after him.
Shortest-path problems can often be solved informally on small networks, but larger networks need a more systematic method. Dijkstra’s algorithm finds the shortest path through a weighted network by comparing the total distance from the starting point, rather than simply choosing the shortest next edge.
The algorithm records the shortest known distance to each vertex and revises these values whenever a shorter route is found. Once a vertex has the smallest unconfirmed total, that distance can be confirmed. This is the key idea behind the refined method students develop in this lesson. Slide 31 provides an animated walkthrough of the algorithm applied to the carpark network.
The algorithm is named after Edsger Dijkstra, a Dutch mathematician and computer scientist who developed it in the 1950s while thinking about how a computer could find the shortest route between locations. His work became foundational in computer science, and shortest-path algorithms based on these ideas are now used in applications such as navigation and network routing. If students ask who Dijkstra was, it is enough to explain that he was one of the pioneers of computer science and that this algorithm is named after him.
Explain that the class has now developed a method that keeps track of the total distance from the starting point, rather than only looking at the next edge. The next test is whether this method can be applied to a different weighted network.
Show Slide 27 with the first road network.
Explain that in this network, the edge weights represent travel time rather than distance. The goal is still to find the path with the smallest total weight.
Provide students with a copy of Supermarket road networks Student Sheet. Allow students time to find possible solutions.
To support students getting started, model the first step only:
- From the supermarket, which vertices can be reached directly?
- What total time should be recorded at each of those vertices?
- Which known total is currently the smallest?
As students work, circulate and ask:
- What is the total time to reach this vertex?
- Is there another way to reach the same vertex with a smaller total?
- Which route currently has the smallest total time?
- Has a shorter route been found that requires an update?
- How can the quickest path be traced back once the total time is known?
Students should:
- keep track of the total time from the supermarket.
- compare different ways of reaching the same vertex.
- update a route if a shorter total time is found.
- identify the quickest path to home.
- justify why the path is quickest.
Students who finish early or are ready to be extended can be challenged to find the shortest path in the more complex second road network.
Bring the class together and compare solutions for the first road network.
Discuss:
- What quickest path was found?
- What was the total time?
- Where did comparing total times matter?
- How was this method different from the greedy algorithm?
- Why is the refined method more repeatable and reliable?
Draw out that the refined method is more reliable because it records and compares total times from the starting point, rather than choosing only the next edge that looks shortest. A solution for the shortest path is available on Slide 28.
The second more complex road network and the accompanying solution are available on Slides 29 and 30 if required. Slide 31 contains an optional animation using Dijkstra's algorithm for finding the shortest path.
Conclude:
A refined algorithm is useful because it gives a repeatable process. Instead of choosing the edge that looks best next, it records and compares total distances from the starting point. This makes the method more reliable and helps justify why a shortest path has been found.
Bring the lesson back to the process used to improve the algorithm.
Discuss:
- What made the greedy algorithm a reasonable first idea?
- How did testing it help reveal its limitation?
- What changed in the refined method?
- Why is it useful to test an improved method on a new network?
Draw out that the greedy algorithm was not a bad starting point. It was simple, clear and easy to apply. However, testing it on a counterexample showed that choosing the shortest next edge was not enough. This created a reason to improve the method by comparing total distances from the starting point.
Conclude:
A useful algorithm often begins as a simple idea. By testing it, finding where it breaks, and refining the method, the algorithm becomes more reliable. The refined shortest-path method gives a repeatable process for comparing total distances and justifying the path with the smallest total weight.