Course contentsShow
← Computer Science
Lesson 1006 of 2,87223. Shortest Path AlgorithmsFree lesson

A* vs Dijkstra's Algorithm

Compare A* with Dijkstra's: A* as guided Dijkstra's using heuristics to reduce search space.

A* vs Dijkstra's Algorithm

What you'll learn: How A* improves upon Dijkstra's algorithm by using heuristics to intelligently guide the search toward the goal.

The Core Relationship

Dijkstra's algorithm explores outward from the source uniformly in all directions, like ripples spreading across water. It uses only one piece of information: the actual distance traveled so far, g(n).

A* is essentially Dijkstra's with a compass. It adds a heuristic function h(n) that estimates the remaining distance to the goal, creating the evaluation function:

f(n) = g(n) + h(n)

This heuristic guides A* to explore more promising directions first, dramatically reducing the search space in most cases.

The Key Difference

  • Dijkstra's: Explores nodes based purely on distance from source (g(n))
  • A:* Explores nodes based on estimated total path cost (g(n) + h(n))

Think of it this way: If you're navigating from New York to Los Angeles, Dijkstra's might explore roads heading toward Canada simply because they're short roads from your starting point. A* uses the heuristic (straight-line distance to LA) to recognize that westward roads are more promising, even if they're slightly longer initially.

When A* Becomes Dijkstra's

When h(n) = 0 for all nodes, A* reduces exactly to Dijkstra's algorithm! This reveals that Dijkstra's is a special case of A* with no guidance information.

The Tradeoff

A* trades guaranteed minimal exploration (Dijkstra's explores optimally without domain knowledge) for practical speed gains when good heuristics exist. With an admissible heuristic, both find the optimal path, but A* typically visits far fewer nodes.

Key Takeaway: A* is Dijkstra's algorithm enhanced with a goal-directed heuristic that reduces the search space by prioritizing nodes likely to lead to shorter paths, making it faster in practice while maintaining optimality when the heuristic is admissible.