Why This Matters
Dijkstra is a general shortest-path algorithm for nonnegative weights. A* is what you reach for when there is one target and a useful heuristic can point the search in the right direction.
Decision Rule
Use Dijkstra when you need distances to many vertices or have no reliable heuristic. Use A* when you need a path to a specific target and can define an admissible heuristic that never overestimates remaining cost.
Comparison Table
| Feature | Dijkstra | A* |
|---|---|---|
| Priority value | g(n) known distance | g(n) + h(n) known plus estimated remaining distance |
| Target | one source to many nodes | one source to one target |
| Heuristic needed | no | yes |
| Correctness condition | nonnegative weights | nonnegative weights plus suitable heuristic |
| Common use | routing tables, all reachable distances | maps, game pathfinding, grid navigation |
Worked Example
On a grid, Dijkstra expands outward in all directions by current distance. A* with Manhattan distance tends to expand toward the goal because cells closer to the goal receive a lower g + h score.
If the heuristic overestimates, A* may skip the actual shortest route. If the heuristic is zero everywhere, A* becomes Dijkstra.
Common Mistakes
| Mistake | Correction |
|---|---|
| Using any heuristic and assuming optimality. | The heuristic must be admissible for the usual shortest-path guarantee. |
| Using A* for all-pairs or all-destination distances. | Dijkstra or Floyd-Warshall may fit better. |
| Forgetting that A* still uses a priority queue. | The priority is g + h, not just h. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
What is g(n) in A*? | Known cost from start to node n. |
What happens when h(n) = 0 for every node? | A* behaves like Dijkstra. |
| Why can a bad heuristic break A*? | It can overestimate and cause the algorithm to prefer a nonoptimal route. |
Exercises
- Beginner: Choose Dijkstra or A* for all distances from one router.
- Beginner: Choose Dijkstra or A* for one path in a grid maze.
- Beginner: Define Manhattan distance on a four-neighbor grid.
- Intermediate: Implement A* on a small grid with blocked cells.
- Intermediate: Compare nodes expanded by Dijkstra and A* on the same maze.
- Challenge: Explain admissible versus consistent heuristics with a counterexample.
References
- MIT OpenCourseWare. 6.006 Lecture 16: Dijkstra, Fall 2011: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-16-dijkstra/
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/