A* Search Algorithm: A Complete Solved Numerical Example

Try A* Search Solver →Read A* Search Theory →

Scenario: Autonomous Drone Delivery Pathfinding

The Objective: Determine the most efficient delivery route for an autonomous drone from the starting facility (S) to its final destination (G) by balancing known flight costs against estimated remaining distances.

Core Mechanics
▼
  • The Master Equation f(n)=g(n)+h(n)f(n) = g(n) + h(n): Always expand the node with the lowest total score. It combines the exact cost traveled so far g(n)g(n) with the estimated cost to finish h(n)h(n).
  • Never Overestimate (Admissibility): To guarantee the shortest path, your heuristic h(n)h(n) must be optimistic. It can guess lower than the true remaining cost, but never higher.
  • Open vs. Closed Lists: Discovered paths wait in the Open List. Once a node is expanded as the cheapest option, it locks into the Closed List and is never evaluated again.
  • The Goal Test Trap: A* only claims victory when the goal is popped from the Open List, not when it is first discovered. This prevents you from accidentally accepting a fast but expensive path!

Step 1: Initial Map Configuration

Before we begin evaluating, here is the full structure of the spatial graph and heuristic values. The algorithm balances both the exact edge costs and the estimated heuristic distances to find the optimal path.

Start Node: S (Heuristic: 14)Goal Node: G (Heuristic: 0)
4
6
3
7
5
4
6
5
14
S
11
A
9
B
5
C
4
D
0
G
Want to edit this data in the live solver?

Step 2: Step-by-Step Resolution Trace

Watch the algorithm evaluate f(n)f(n) scores, manage the Open and Closed lists, and aggressively prune sub-optimal paths.

1

Evaluating Node: S

g(S)=0g (S) = 0h(S)=14h(S) = 14f(S)=14f(S) = 14
Open List

[ S(14) ]

Closed List

[ ]

Evaluating Neighbors
Evaluated neighbor A (via SA)
f=g(4)+h(11)=f = g (4) + h(11) = 15
Evaluated neighbor B (via SB)
f=g(6)+h(9)=f = g (6) + h(9) = 15
2

Evaluating Node: SB

g(B)=6g (B) = 6h(B)=9h(B) = 9f(B)=15f(B) = 15
Open List

[ SB(15), SA(15) ]

Closed List

[ S(14) ]

Evaluating Neighbors
Evaluated neighbor D (via SBD)
f=g(11)+h(4)=f = g (11) + h(4) = 15
3

Evaluating Node: SBD

g(D)=11g (D) = 11h(D)=4h(D) = 4f(D)=15f(D) = 15
Open List

[ SBD(15), SA(15) ]

Closed List

[ S(14), SB(15) ]

Evaluating Neighbors
Evaluated neighbor G (via SBDG)
f=g(16)+h(0)=f = g (16) + h(0) = 16
4

Evaluating Node: SA

g(A)=4g (A) = 4h(A)=11h(A) = 11f(A)=15f(A) = 15
Open List

[ SA(15), SBDG(16) ]

Closed List

[ S(14), SB(15), SBD(15) ]

Evaluating Neighbors
✂️Evaluated neighbor B (via SAB)Skipped: Node B is already in the Closed List (already fully explored).
f=g(7)+h(9)=f = g (7) + h(9) = 16
Evaluated neighbor C (via SAC)
f=g(11)+h(5)=f = g (11) + h(5) = 16
5

Evaluating Node: SBDG

g(G)=16g (G) = 16h(G)=0h(G) = 0f(G)=16f(G) = 16
Open List

[ SBDG(16), SAC(16) ]

Closed List

[ S(14), SB(15), SBD(15), SA(15) ]

Evaluating Neighbors
No valid neighbors to explore (Dead End).
6

Goal Reached: SBDG

Goal Found
Open List

[ SAC(16) ]

Closed List

[ S(14), SB(15), SBD(15), SA(15), SBDG(16) ]

Step 3: Final Optimal Path

Optimal Path Reached

S → B → D → G
Total Path Cost:16

Final Takeaway

Notice the algorithm's discipline at Step 4! Even though SBDG(16) is right next to the goal, A* pauses to explore SA(15) strictly because 15 is less than 16. During this detour, it intelligently rejects the A→B path because B is already in the Closed List, proving we found a cheaper way there earlier.