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

Introduction to A* Search

Overview of A* as an informed search algorithm that uses heuristics to find optimal paths efficiently.

Introduction to A* Search

You'll learn what A* search is and how it improves upon traditional shortest-path algorithms by using heuristics to guide the search toward the goal more efficiently.

The Core Idea

Imagine you're navigating from your home to a friend's house using a map. Dijkstra's algorithm explores outward in all directions equally, like ripples in a pond, checking every possible route methodically. But you, being smarter, would prioritize streets that look like they're heading toward your destination—you use intuition about which direction is promising.

A (pronounced "A-star") does exactly this.* It's an informed search algorithm that combines two pieces of information:

  1. Actual cost so far (like Dijkstra's distance from start)
  2. Estimated cost to goal (a heuristic guess about remaining distance)

By adding these together, A* prioritizes exploring paths that seem most promising—those likely to lead to the shortest total path. This makes it faster than Dijkstra's for many real-world problems, especially when you have a single target destination.

Why It Matters

Unlike Dijkstra's, which blindly explores equally in all directions, A* uses a heuristic function (often denoted h(n)) to estimate how far each node is from the goal. This guides the search like a compass, reducing wasted exploration. When the heuristic is well-designed, A* finds optimal paths much faster while still guaranteeing correctness.

Key Takeaway: A* search enhances Dijkstra's algorithm by incorporating heuristic estimates to intelligently prioritize which paths to explore, making shortest-path searches dramatically more efficient when you know where you're going.