Shortest Path on a Map
About this lesson, for parents and teachers
How does a map app find the fastest way out of thousands of roads? It sends out a search that spreads like a ripple in a pond. Draw some walls and watch it work.
Ages 9–11 · about 8 minutes · builds on Find the Way Through the Maze · leads to How the Internet Sends Messages, Reinforcement Learning: An Agent Learns a Maze
Try this
- Press Search. Watch the wave spread from S, writing how many steps away each square is.
- Drag on the map to draw walls (drag on a wall to erase). Make the shortest route much longer.
- Trap G so there is no route at all, and see what the search reports.
- Predict which square the wave will reach last, then search to check.
How it works
The search starts at S, which is 0 steps away. First it visits every square next to S: those are 1 step away. Then every new square next to those: 2 steps away. And so on. Because it finishes all of the 1-step squares before any 2-step square, it spreads out evenly like a ripple. This is called breadth-first search, or BFS.
Every square remembers which square the wave came from. When the wave touches G, the computer follows those arrows backwards from G to S. That gives the route, and it is guaranteed to be the shortest one, because the wave reached G at the earliest possible step. Following arrows backwards like this is called backtracking the path.
Walls change everything. The wave cannot go through them, so it flows around, and the numbers grow. If walls cut G off completely, the wave fills every square it can reach and stops. The search has proven there is no route, without guessing. Notice how the wave pours through a gap and then spreads out again on the other side, like water.
Computers keep the squares waiting to be visited in a queue: first in, first out, like a line at a shop. Real maps are graphs: places are dots and roads are lines between them. Map apps use smarter cousins of BFS, like Dijkstra's algorithm and A*, which also count how long each road takes.
Where engineers use this
Map and delivery apps, video game characters that chase you, and internet routers all use graph search like this to find good routes. Robot vacuums use it to plan a path around furniture.
Words to know
- Breadth-first search (BFS)
- A search that visits everything 1 step away, then 2 steps, then 3, so it always finds the shortest route first.
- Graph
- A set of places (nodes) connected by links (edges), like towns and roads.
- Queue
- A waiting line where the first thing in is the first thing out.
- Shortest path
- The route between two places that uses the fewest steps.
Talk about it
Goal: Watch a search spread out like a ripple to find the shortest route, the idea behind map apps.
- When you walk somewhere new, how do you decide which way to go? Is it like the wave?
- Why might the shortest route not always be the fastest one in a real city?
- How could the wave tell that G was impossible to reach?
Without a screen: Draw a grid on paper (or use floor tiles) and put coins or books down as walls. Mark a start square 0, write 1 in every square touching it, 2 in every square touching a 1, and so on, until you reach the goal. Then walk back down the numbers to find the shortest route.
Curriculum links: CSTA K-12 1B-AP-08 (compare and refine multiple algorithms for the same task) and 1B-AP-11 (decompose problems into smaller parts); AP Computer Science Principles AAP-4.A (algorithms and efficiency)
Questions
How do map apps find the shortest route?
They treat roads as a graph and run a search that explores outward from where you are, keeping track of the shortest distance to each place. Breadth-first search is the simplest version; real apps use Dijkstra's algorithm or A*, which also weigh travel time.
What is breadth-first search for kids?
It is a way of searching that checks everything 1 step away first, then 2 steps, then 3, like a ripple spreading in water. Because it goes in order of distance, the first time it reaches the goal it has found the shortest route.
What is the difference between BFS and DFS?
Breadth-first search spreads out evenly in all directions. Depth-first search follows one path as far as it can before backing up. BFS finds the shortest route on a grid; DFS finds a route but not always the shortest.