# Dijkstra vs A\* for Robot Path Planning

> Dijkstra and A\* compared on a grid: cost function, heuristics, memory and which suits a small robot.

Canonical: https://roboticsengineering.in/dijkstra-vs-a-star-robot-planning/ | Published: 2026-11-09 | Updated: 2026-11-09 | Author: Jignesh S Panchal

**Dijkstra and A\* both find the lowest-cost path on a grid or graph, but Dijkstra spreads out evenly in all directions while A\* adds a heuristic estimate of the remaining distance and so heads toward the goal. With a valid heuristic A\* returns the same cost as Dijkstra and usually visits far fewer cells.**

## Key takeaways

- Dijkstra expands cells in order of cost-so-far g, so it explores a growing blob around the start.
- A\* expands cells in order of f = g + h, where h is an estimate of the remaining cost to the goal.
- A\* stays optimal only if h never overestimates, a property called admissible.
- With h = 0, A\* becomes Dijkstra, so Dijkstra is the special case with no goal knowledge.

## What Each Algorithm Does

Dijkstra’s algorithm finds the cheapest path from a start node to all other nodes by always expanding the node with the smallest known cost from the start. A\* is a variant that targets a single goal and uses extra knowledge to avoid exploring in directions that lead away from it.

Both keep an open list of nodes waiting to be expanded, pick the best one, look at its neighbours, and update their costs if a cheaper route is found. They differ only in how they rank the open list. Both work on a grid of cells, a graph of waypoints or a road-like map, and both appear inside planners such as the one in the [ROS 2 Nav2 tutorial](https://roboticsengineering.in/ros2-nav2-tutorial/).

## Cost Function Difference

The cost function is the number used to rank nodes. Dijkstra ranks by `g(n)`, the cost of the best path found from the start to node n. A\* ranks by `f(n) = g(n) + h(n)`, where `h(n)` is a guess of the cheapest remaining cost from n to the goal.

The effect is that Dijkstra grows a circle (or diamond on a 4-connected grid) of equal cost around the start, and only reaches the goal when that circle gets big enough. A\* tilts the search, so nodes that are on the way to the goal look cheaper than nodes that are not. The cell costs can include more than distance, for example higher cost near walls, which is how costmaps shape the path, as discussed in the [Nav2 costmap tuning guide](https://roboticsengineering.in/nav2-costmap-tuning-guide/).

## Heuristic Requirements

A heuristic is the estimate h(n). To keep A\* optimal, h must be admissible, meaning it never overestimates the true remaining cost. A stronger property, consistency, means h does not drop by more than the step cost between neighbours, and with it A\* never needs to re-expand a node.

For grids, the usual choices depend on the allowed moves:

- **4-connected moves, unit cost:** Manhattan distance `|dx| + |dy|`.
- **8-connected moves, diagonal cost 1.414:** octile distance, which is `max(|dx|,|dy|) + 0.414 x min(|dx|,|dy|)`.
- **Any direction:** straight-line Euclidean distance, which is always safe but weaker than the matching grid heuristic.

Using Manhattan distance on an 8-connected grid can overestimate, so the path may no longer be the cheapest. Multiplying h by a weight above 1 makes the search faster but gives up the optimality guarantee, which can be an acceptable trade on a small robot if you accept slightly longer paths.

## Grid Example

Assumptions: an empty 5 by 5 grid, 4-connected moves with cost 1 each, start at `(0, 0)` and goal at `(4, 0)`, using Manhattan distance for A\*.

**Dijkstra.** It expands cells in order of g. All cells with `g < 4` come first. Cells with `x + y` equal to 0, 1, 2 and 3 number `1 + 2 + 3 + 4 = 10`. Then it reaches cells at `g = 4`, which are `(4,0)`, `(3,1)`, `(2,2)`, `(1,3)` and `(0,4)`, 5 cells in a tie. The goal is one of them, so Dijkstra expands between 10 and 15 cells depending on tie order.

**A\*.** For a cell on the straight row, such as `(2,0)`, `g = 2` and `h = 2`, so `f = 4`. For a cell off the row, such as `(0,1)`, `g = 1` and `h = 4 + 1 = 5`, so `f = 6`. The row cells always have the lowest f, so A\* expands only `(0,0)`, `(1,0)`, `(2,0)`, `(3,0)` and `(4,0)`, which is 5 cells.

| Algorithm | Cells expanded | Path cost |
| --- | --- | --- |
| Dijkstra | 10 to 15 | 4 |
| A\* (Manhattan) | 5 | 4 |

Both give a path of cost 4, and A\* did the same job with about a third to a half of the expansions. With obstacles, the saving depends on the map: a wall that forces a detour makes A\* explore more, though usually still fewer cells than Dijkstra. The [maze solver robot](https://roboticsengineering.in/projects/maze-solver-robot-arduino/) works in a grid like this one, so you can try both on a real maze map.

## Memory and Speed

Both algorithms store a cost for every cell they have seen and an open list, so memory grows with the number of visited cells, and the open list is usually a priority queue such as a binary heap. In the worst case A\* can visit as many cells as Dijkstra, and each step costs a little more because of the heuristic. On a bigger map the saving from fewer cells usually outweighs this.

For a microcontroller, memory is the real limit. A grid of 100 by 100 cells needs 10,000 entries, and at two bytes each for the cost that is about 20 KB before the open list, which is too much for many 8-bit boards, since an Arduino Uno has 2 KB of SRAM. Use a coarse grid, a smaller region around the robot, or run the planner on a bigger computer or ROS 2 on a single-board computer, and send waypoints to the microcontroller. Start with the [SLAM for beginners](https://roboticsengineering.in/slam-for-beginners/) overview to see where the map comes from.

## Which Suits a Small Robot

For one start and one goal on a map, A\* with an admissible heuristic is the usual choice, since it returns the same path as Dijkstra with less work. Dijkstra is better when you want the cheapest path from one start to every cell, such as building a distance field from the goal outward, which some wall-following and flood-fill maze strategies resemble. For a tiny maze with a few dozen cells, both are instant and the simpler code wins.

A practical path for a student project is to write Dijkstra first, since it is a short program and easy to check, then change the ranking to g plus h and compare the number of expanded cells. See odometry and pose tracking in the [differential drive odometry project](https://roboticsengineering.in/projects/differential-drive-odometry-arduino/) for following the resulting path, and more planning topics in the [Learn hub](https://roboticsengineering.in/learn/).

## How to check this yourself

1. Draw a 5 by 5 grid on paper, mark a start and a goal, and run Dijkstra by hand, writing g values on each cell.
2. Repeat with f = g + h using Manhattan distance, and count expanded cells for each.
3. Add a wall of blocked cells and repeat both runs to see how the saving changes.
4. Code both versions with a counter that increments each time a cell is expanded, and print it.

## Common mistakes

- Using a heuristic that overestimates, so A\* returns a longer path than needed.
- Using Manhattan distance on an 8-connected grid.
- Forgetting to update a node’s cost when a cheaper route to it is found.
- Choosing a grid so fine that the memory runs out on the microcontroller.

## Quick checklist

- Decide the allowed moves and their costs.
- Choose a heuristic that matches them and never overestimates.
- Use a priority queue for the open list.
- Count expanded cells to compare the two algorithms.
- Check memory against your board before choosing the grid size.

## Frequently asked questions

### What is the difference between Dijkstra and A\*?

Dijkstra ranks cells by the cost from the start only, so it explores outward in all directions. A\* ranks by that cost plus a heuristic estimate of the remaining distance to the goal, so it heads toward the goal and usually expands fewer cells while returning an equally cheap path.

### Is A\* always faster than Dijkstra?

Usually, but not always. With a poor heuristic, or a map full of obstacles that force a detour, A\* can visit nearly as many cells as Dijkstra, and each step costs slightly more. With h equal to zero it behaves exactly like Dijkstra. Time both on your own map.

### Which heuristic should I use for A\* on a grid?

Use Manhattan distance for 4-connected moves and octile distance for 8-connected moves with diagonal cost 1.414. Euclidean distance is also safe but weaker. The key rule is that the heuristic must never overestimate the true remaining cost, or the path may not be the cheapest.

## Related reading

- [ROS 2 control tutorial](https://roboticsengineering.in/ros2-control-tutorial/): how planned velocities reach the wheels.

## About the author and how this is kept accurate

Written, checked and maintained by [Jignesh Panchal](https://www.linkedin.com/in/jignesh-s-panchal/) of [Jaadu Digital](https://jaadudigital.com/). Figures in worked examples come from the stated assumptions, not from a bench test of our own. Read the [editorial standard](https://roboticsengineering.in/editorial-standard/), follow the author on [LinkedIn](https://www.linkedin.com/in/jignesh-s-panchal/), or [send a correction](https://roboticsengineering.in/contact/). Last reviewed: November 2026.
