Finding a route
A map app, a game character walking around a wall, a network choosing a path for your data: all of them solve the same problem. Given a start, a goal and a set of places connected by links, find a good route.
"Good" is the catch. It might mean the fewest steps, or the lowest total cost when some steps are more expensive than others.
Every animation on this page uses the same small map:
- S is the start and G is the goal.
- Moving onto a plain cell (road) costs 1.
- Moving onto a mud cell costs 5.
- Dark cells are walls.
There is a short, straight route through the mud, and a longer way round on the road.
Try all four
- mud (cost 5)
- explored
- the route found
Start. S is the start and G is the goal. Road costs 1 per step and mud costs 5. Walls block the way.
- Cells expanded
- 0
- Route steps
- –
- Route cost
- –
BFS: fewest steps
Breadth-first search explores in rings. First every cell 1 step from the start, then every cell 2 steps away, then 3. The first time it reaches the goal, it has found a route with the fewest steps.
- mud (cost 5)
- explored
- the route found
Start. S is the start and G is the goal. Road costs 1 per step and mud costs 5. Walls block the way.
- Cells expanded
- 0
- Route steps
- –
- Route cost
- –
It finishes with a route of 8 steps. But look where the route goes: straight through the mud. It costs 36. BFS counts steps and never looks at what a step costs.
Good at
- Simple, and it finds the fewest steps
- The right tool when every step costs the same
Where it bites
- Blind to cost: on this map its answer is fast to find and wrong
Dijkstra: lowest cost
Dijkstra's algorithm always expands the cheapest place it has reached so far. It keeps a running cost for every cell it has discovered, and repeatedly takes the cell with the lowest one.
The start has cost 0
Every other cell is unknown.
Take the cheapest cell not yet finished
Its cost is now final. Nothing cheaper can turn up later, because every other option already costs more.
Look at its neighbours
Cost to reach a neighbour = this cell's cost + the cost of stepping onto the neighbour. If that beats what the neighbour had, write it down.
Repeat until the goal is the cheapest cell
Then follow the trail backwards to read off the route.
- mud (cost 5)
- explored
- the route found
Start. S is the start and G is the goal. Road costs 1 per step and mud costs 5. Walls block the way.
- Cells expanded
- 0
- Route steps
- –
- Route cost
- –
This time the route goes around on the road: 14 steps at a cost of 14, less than half of what BFS paid. Notice that the mud cells are left for last. They are expensive, so cheaper cells always get their turn first.
Good at
- Finds the cheapest route when costs differ
- Gives the cheapest cost to every cell it finishes, not just the goal
Where it bites
- Spreads out evenly in every direction, including directly away from the goal
- Does not work if any link has a negative cost
A*: lowest cost, with a sense of direction
Dijkstra knows nothing about where the goal is. A* (say "A star") adds a hint: a quick estimate of how far each cell still is from the goal. Here the estimate is simply rows apart plus columns apart.
Instead of "cheapest so far", A* expands the cell with the lowest cost so far + estimated distance left. Cells heading towards the goal look better than cells heading away.
- mud (cost 5)
- explored
- the route found
Start. S is the start and G is the goal. Road costs 1 per step and mud costs 5. Walls block the way.
- Cells expanded
- 0
- Route steps
- –
- Route cost
- –
It finds the same route at the same cost and expands fewer cells to get there. On large open maps the saving is dramatic, which is why games and map apps use it.
Bellman-Ford: slow and thorough
Bellman-Ford does not pick the next cell cleverly at all. It goes over every link on the map and asks "does this link give a cheaper way to reach the cell at its end?". Then it does the whole thing again, and again, until a full pass changes nothing.
- mud (cost 5)
- explored
- the route found
Start. S is the start and G is the goal. Road costs 1 per step and mud costs 5. Walls block the way.
- Links checked
- 0
- Route steps
- –
- Route cost
- –
Same answer as Dijkstra, after far more work. So why does it exist? Because it copes with something the others cannot: links with a negative cost, where taking a step gives something back. Dijkstra assumes a finished cell can never get cheaper, and a negative link breaks that. Bellman-Ford makes no such assumption. It can also report when a map contains a loop that gets cheaper every time round, in which case there is no cheapest route at all.
Side by side
| Finds | Looks at cost | Typical use | |
|---|---|---|---|
| BFS | Fewest steps | No | Mazes, grids and networks where every step is equal |
| Dijkstra | Cheapest route | Yes | Road maps, network routing |
| A* | Cheapest route | Yes, plus a distance estimate | Games, maps, anywhere a goal position is known |
| Bellman-Ford | Cheapest route | Yes, even negative | Money and currency graphs, some network protocols |
Key takeaways
- BFS explores in rings and finds the fewest steps. It ignores cost.
- Dijkstra always expands the cheapest cell reached so far and finds the cheapest route.
- A* adds an estimate of the distance left, so it wastes less effort in the wrong direction.
- Bellman-Ford re-checks every link until nothing improves. It is slow but handles negative costs.
- Decide first what "best" means: fewest steps and lowest cost can be different routes.