# A* Pathfinding Explained: Why It Beats Dijkstra > Learn how the A* pathfinding algorithm works, why it outperforms Dijkstra, and see a Python implementation with heuristic functions. - Author: Shawn Ng (https://shawnng.com/about) - Published: 2026-01-25 - Updated: 2026-09-30 - Canonical URL: https://shawnng.com/posts/astar-pathfinding-vs-dijkstra - Topics: algorithms, pathfinding, a-star, robotics ## Key takeaways - A* is Dijkstra with direction: it always expands the node with the lowest f(n) = g(n) + h(n). - The heuristic must be admissible, meaning it never overestimates the true cost to the goal, or A* can miss the shortest path. - If the heuristic returns zero for every node, A* degrades into Dijkstra's algorithm and explores in all directions. - On a 50x50 open grid A* expanded 99 nodes against 2,500 for Dijkstra, but in a maze with a single route the advantage nearly disappears. - A* keeps every visited node in memory, so in high-dimensional state spaces planners like RRT are preferred. If you have ever used Google Maps, played a strategy game, or watched a robot navigate a warehouse, you have seen pathfinding in action. The algorithm behind most of that is **A* (A-star)**, and it is one of the most elegant ideas in computer science. It finds the shortest path between two points, just like [Dijkstra's algorithm](https://shawnng.com/posts/dijkstras-algorithm-explained), but it does it significantly faster by being smarter about where it looks. Check out the full video on my YouTube channel [Divide and Quantum](https://www.youtube.com/watch?v=kZDh6m_Y7ME). ## The Problem: Finding the Shortest Path Given a graph (a grid, a road network, a game map) with weighted edges, find the path from a start node to a goal node that minimizes total cost. Dijkstra's algorithm solves this problem. So does A*. The difference is how much work they do along the way. **Dijkstra's algorithm** explores nodes in order of their distance from the start. It expands outward in every direction, like a ripple in a pond, until it reaches the goal. This guarantees the shortest path, but it wastes time exploring nodes that are in the completely wrong direction. Both algorithms also assume non-negative edge weights; when weights can go negative you want [Bellman-Ford and its negative-cycle detection](https://shawnng.com/posts/bellman-ford-arbitrage) instead. **A\*** adds a simple but powerful idea: use a **heuristic** to estimate how far each node is from the goal, and prioritize nodes that appear to be closer. Instead of expanding blindly in all directions, A* focuses its search toward the destination. ## The Core Formula: f = g + h Every node in A* has three values: - **g(n)**: the actual cost from the start node to node n (same as Dijkstra) - **h(n)**: the estimated cost from node n to the goal (the heuristic) - **f(n) = g(n) + h(n)**: the total estimated cost of the path through node n A* always expands the node with the lowest f(n) value. This is the key insight: by combining what we know (g) with what we estimate (h), we make much better decisions about which nodes to explore next. ### Choosing a Good Heuristic The heuristic h(n) is what makes A* fast, but it has to follow one rule to guarantee the shortest path: it must be **admissible**, meaning it never overestimates the true cost to the goal. Common heuristics for grid-based pathfinding: - **Manhattan distance**: `|x1 - x2| + |y1 - y2|`, used when movement is restricted to four directions (up, down, left, right) - **Euclidean distance**: `sqrt((x1 - x2)^2 + (y1 - y2)^2)`, used when movement can go in any direction - **Chebyshev distance**: `max(|x1 - x2|, |y1 - y2|)`, used when diagonal movement costs the same as cardinal movement If h(n) = 0 for all nodes, A* degrades into Dijkstra's algorithm. The better your heuristic, the fewer nodes A* needs to explore. ## A* in Python Here is a complete A* implementation for a 2D grid: ```python import heapq def astar(grid, start, goal): """ Find the shortest path on a 2D grid using A*. grid: 2D list where 0 = walkable, 1 = wall start: (row, col) tuple goal: (row, col) tuple Returns: list of (row, col) tuples representing the path """ rows, cols = len(grid), len(grid[0]) def heuristic(a, b): # Manhattan distance return abs(a[0] - b[0]) + abs(a[1] - b[1]) # Heap entries are (f, -g, node). On a tie in f, the node with the # larger g (further along its path) comes out first, which stops A* # from fanning out across every equally good cell on an open grid. open_set = [] heapq.heappush(open_set, (heuristic(start, goal), 0, start)) came_from = {} g_score = {start: 0} f_score = {start: heuristic(start, goal)} directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while open_set: current_f, _, current = heapq.heappop(open_set) if current == goal: # Reconstruct path path = [] while current in came_from: path.append(current) current = came_from[current] path.append(start) return path[::-1] for dr, dc in directions: neighbor = (current[0] + dr, current[1] + dc) if (0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and grid[neighbor[0]][neighbor[1]] == 0): tentative_g = g_score[current] + 1 if tentative_g < g_score.get(neighbor, float('inf')): came_from[neighbor] = current g_score[neighbor] = tentative_g f_score[neighbor] = tentative_g + heuristic(neighbor, goal) heapq.heappush(open_set, (f_score[neighbor], -tentative_g, neighbor)) return [] # No path found ``` And here is how you would use it: ```python grid = [ [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 0], ] path = astar(grid, (0, 0), (4, 4)) print(path) # [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)] ``` ## A* vs. Dijkstra: A Direct Comparison Let's compare the two algorithms on the same problem to see why A* wins. ### Dijkstra's Approach Dijkstra expands nodes in concentric rings outward from the start. On a 100x100 grid with the goal in the far corner, Dijkstra might visit **most of the 10,000 cells** before finding the path. ```python def dijkstra(grid, start, goal): rows, cols = len(grid), len(grid[0]) open_set = [] heapq.heappush(open_set, (0, start)) came_from = {} dist = {start: 0} directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while open_set: current_dist, current = heapq.heappop(open_set) if current == goal: path = [] while current in came_from: path.append(current) current = came_from[current] path.append(start) return path[::-1] for dr, dc in directions: neighbor = (current[0] + dr, current[1] + dc) if (0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and grid[neighbor[0]][neighbor[1]] == 0): new_dist = dist[current] + 1 if new_dist < dist.get(neighbor, float('inf')): dist[neighbor] = new_dist came_from[neighbor] = current heapq.heappush(open_set, (new_dist, neighbor)) return [] ``` ### The Performance Difference On an open grid, A* with Manhattan distance explores nodes in a narrow corridor toward the goal. Dijkstra explores a full expanding circle. The difference is dramatic: | Scenario (corner to corner) | Dijkstra (nodes expanded) | A* (nodes expanded) | |---|---|---| | 50x50 open grid | 2,500 | 99 | | 100x100, 15% random walls | 8,454 | 791 | | 51x51 maze with a single route | 761 | 680 | These are measured with the two functions above on seeded grids, counting nodes taken off the heap before the goal. The tie-break matters: without it, A* on the open grid expands all 2,500 cells too, because every cell on the way has the same `f`. In open spaces, A* can be an order of magnitude faster. In tight mazes where there is only one possible path, the advantage shrinks because the heuristic cannot eliminate many options. ## When A* Struggles A* is not always the best choice. ### High-Dimensional Spaces A* keeps all visited nodes in memory. In problems with millions of possible states (like robot arm planning in 6D configuration space), the memory usage becomes prohibitive. Algorithms like **RRT (Rapidly-exploring Random Trees)** are often preferred. ### Poor Heuristics If your heuristic is not admissible (it overestimates), A* may not find the shortest path. If your heuristic is admissible but loose (much lower than the true cost), A* degrades toward Dijkstra-level performance. ### Dynamic Environments Standard A* assumes the graph doesn't change during search. For environments where edges change in real time (think traffic or a robot avoiding moving obstacles), variants like **D\* Lite** are used instead. ## Real-World Applications of A* Pathfinding A* and its variants power some of the most important systems in technology: - **Google Maps / Waze**: Road networks are graphs. Turn-by-turn navigation uses A* variants combined with hierarchical decomposition (contraction hierarchies) for speed. - **Video games**: Nearly every strategy game, RPG, and simulation uses A* for NPC movement. The game industry has developed dozens of A* optimizations like Jump Point Search. - **Warehouse robotics**: Amazon's Kiva robots use pathfinding algorithms to navigate warehouse floors without colliding, coordinating hundreds of robots simultaneously. - **Autonomous vehicles**: Self-driving cars use A* variants in their motion planning stack to find collision-free paths through traffic. Pathfinding only answers where to go; knowing where the robot actually is falls to a different algorithm, [the Kalman filter that guided Apollo](https://shawnng.com/posts/kalman-filter-apollo). ## Key Takeaways A* is Dijkstra with direction. By adding a heuristic estimate of remaining distance, it focuses the search toward the goal and dramatically reduces the number of nodes explored. The formula `f = g + h` is simple, but its impact on performance is profound. If you ever need to find the shortest path and you know where the goal is, A* should be your first choice. ## Frequently asked questions ### Is A* always faster than Dijkstra? No. A* is usually much faster because its heuristic focuses the search toward the goal, but with a zero or very loose heuristic it degrades toward Dijkstra. In a tight maze with only one possible path, both explore almost the same number of nodes. ### What is the difference between A* and Dijkstra? A* adds a heuristic h(n) that estimates the remaining cost to the goal and expands the node with the lowest f(n) = g(n) + h(n). Dijkstra uses only g(n), the cost from the start, so it expands outward in every direction. ### Which heuristic should I use for A* on a grid? Use Manhattan distance when movement is restricted to four directions, Euclidean distance when movement can go in any direction, and Chebyshev distance when diagonal movement costs the same as cardinal movement. ### Does A* always find the shortest path? Yes, as long as the heuristic is admissible and never overestimates the true cost to the goal. A heuristic that overestimates can make A* return a path that is not the shortest. ## Sources - Peter Hart, Nils Nilsson, Bertram Raphael (1968). [A Formal Basis for the Heuristic Determination of Minimum Cost Paths](https://doi.org/10.1109/TSSC.1968.300136). IEEE Transactions on Systems Science and Cybernetics. - E. W. Dijkstra (1959). [A note on two problems in connexion with graphs](https://doi.org/10.1007/BF01386390). Numerische Mathematik. - S. M. LaValle (1998). [Rapidly-exploring random trees: A new tool for path planning](https://lavalle.pl/papers/Lav98c.pdf). Computer Science Dept., Iowa State University (TR 98-11). - Sven Koenig, Maxim Likhachev (2002). [D* Lite](https://cdn.aaai.org/AAAI/2002/AAAI02-072.pdf). AAAI-02 Proceedings. - Daniel Harabor, Alban Grastien (2011). [Online Graph Pruning for Pathfinding On Grid Maps](https://doi.org/10.1609/aaai.v25i1.7994). Proceedings of the AAAI Conference on Artificial Intelligence. - Peter R. Wurman, Raffaello D'Andrea, Mick Mountz (2008). [Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses](https://doi.org/10.1609/aimag.v29i1.2082). AI Magazine.