About this experiment
Route planners in maps, robots and video games all solve the same problem: find the cheapest way from a start to a goal. On this grid each step onto road costs 1, a step into mud costs 5 and walls cannot be crossed. Watch three classic algorithms spread out from S. Breadth-first search counts steps and ignores the mud, Dijkstra always explores the cheapest cell next, and A* adds a guess of the distance still to go so it can head straight for the goal. Paint your own maps and compare how much work each one does.
Learning goals
- Represent a map as a graph of cells joined to their neighbours, with a cost on each step
- Describe how breadth-first search explores in rings of equal step count
- Explain why Dijkstra finds the cheapest path when steps have different costs
- Explain how the A* heuristic reduces the number of cells explored without losing the best path
- Compare algorithms by the cost of the path they find and the amount of work they do
How to use it
- 1Choose BFS and press Search. Does the path it finds go through the mud? Read its cost in the table.
- 2Choose Dijkstra and search again. Compare the path and its cost with BFS.
- 3Choose A*. Is its path cost the same as Dijkstra? How many fewer cells did it explore?
- 4Watch the blue frontier during a search. How is its shape different for Dijkstra and A*?
- 5Paint a wall to close the road around the mud. Which algorithm changes its path, and why?
- 6Press Clear map and drag S and G apart. With no obstacles, how many cells does each algorithm explore?
The model
Assumptions
- Moves are up, down, left and right only. Entering a cell costs 1 on road and 5 in mud; walls cannot be entered.
- BFS treats every step as cost 1 while searching, so it finds the path with the fewest steps. Its cost in the table is the true cost of that path including mud.
- When two cells have the same priority, the one added first is explored first, so every run with the same map gives exactly the same order.
- The search stops as soon as the goal is taken off the frontier, which is when its cheapest cost is known.
Try this in class
- Q1Why can BFS give a more expensive path than Dijkstra, even though it uses fewer steps?
- Q2If every cell were road, would BFS and Dijkstra find paths with the same cost? Why?
- Q3What would happen to A* if the guess h were ten times the Manhattan distance?
- Q4Why does A* explore fewer cells when the goal is in an open area, but about as many as Dijkstra in a maze?
- Q5A satnav finds a fast route across a country with millions of road junctions in under a second. Which ideas from this lab help make that possible?
Frequently asked questions
Which algorithm is the best?
It depends on the problem. BFS is simple and correct when every step costs the same. Dijkstra handles different costs. A* gives the same answer as Dijkstra while exploring fewer cells, if a good estimate of the distance to the goal is available.
What is the frontier?
The frontier is the set of cells that have been reached but not yet explored. Each algorithm takes one cell off the frontier at a time; the difference between them is only the rule for which cell to take next.
Can these algorithms handle negative costs?
Dijkstra and A* assume that no step has a negative cost. With negative costs a cell that was settled early could later turn out to have a cheaper route, and a different algorithm such as Bellman-Ford is needed.