Pointer Walk

Pathfinding: BFS, Dijkstra, Bellman-Ford and A*

Four ways to find a route on the same map. One of them finds the fewest steps and the most expensive route.

AlgorithmsIntermediate14 min read

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

BFSInteractive
Algorithm
S5555555G
  • 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.

BFSInteractive
S5555555G
  • 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.

  1. The start has cost 0

    Every other cell is unknown.

  2. 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.

  3. 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.

  4. Repeat until the goal is the cheapest cell

    Then follow the trail backwards to read off the route.

DijkstraInteractive
S5555555G
  • 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.

A*Interactive
S5555555G
  • 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.

Bellman-FordInteractive
S5555555G
  • 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

FindsLooks at costTypical use
BFSFewest stepsNoMazes, grids and networks where every step is equal
DijkstraCheapest routeYesRoad maps, network routing
A*Cheapest routeYes, plus a distance estimateGames, maps, anywhere a goal position is known
Bellman-FordCheapest routeYes, even negativeMoney 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    9 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress