Algorithm Guidecomplexity: O(E)

A* Search

A heuristic-based shortest-path algorithm that expands the node with the smallest f(n) = g(n) + h(n) first. With an admissible heuristic it guarantees the optimal path, and it's the standard tool for pathfinding, game AI, and robot navigation.

01A* Search

Explore How It Works

Starting A* search. Expand the node with the smallest f(n)=g(n)+h(n) first; as long as the heuristic never overestimates the real cost, it guarantees the optimal path.

Pop A (f=10), the smallest f in the open set, and expand it. Compute the g and f values of neighbors B, C.

Reaching B actually costs 1, and the estimate of what's left is 8 — together f=9, which goes into the open set.

C costs 3 so far plus an estimate of 5, giving f=8. That beats B's 9, so it is examined first.

Pop C (f=8), the smallest f, and expand it. Choosing it before B (f=9) is exactly why A* is faster than Dijkstra.

D costs 4 so far plus an estimate of 3, giving f=7 — the most promising route yet.

Pop D (f=7), the smallest f, and expand it.

G costs 5 with an estimate of 0 — we've arrived, so its f is 5 as well.

Pop G (f=5) — it matches the goal. Optimal path A → C → D → G (cost 5). B is pruned and never expanded.

Search complete · optimal path A → C → D → G (cost 5). The heuristic steered the search direction effectively.

Live Python

1def a_star(graph, start, goal, h):

# open = [(A, 10)]

2 open_set = [(h[start], start)] # min-heap by f

3 g = {start: 0}

# g[A] = 0

4 parent = {start: None}

5 closed = set()

6 while open_set:

7 f_cur, current = heappop(open_set)

8 if current == goal:

9 return reconstruct(parent, goal)

10 closed.add(current)

11 for nb, w in graph[current]:

12 if nb in closed:

13 continue

14 tentative = g[current] + w

15 if tentative < g.get(nb, INF):

16 g[nb] = tentative

17 parent[nb] = current

18 heappush(open_set,

19 (tentative + h[nb], nb))

20 return None

1 / 10

02 Understand It Simply

For Everyone

🔑How It Works

Expands whichever node has the smallest f, the cost so far g plus an estimate h of what remains. If h never overestimates, the shortest path is guaranteed.

💡In Plain Words

Expands nodes with the smallest f — actual cost g plus estimated remaining h.

With a good estimate, it beats Dijkstra.

📍Where It's Used

–Game pathfinding
–robot navigation
–route search

03 Python Implementation

A clean, readable reference implementation of the core logic of A* Search.

core_implementation.py

from heapq import heappush, heappop

def a_star(graph, start, goal, h):
    open_set = [(h[start], start)]
    g = {start: 0}
    parent = {start: None}
    closed = set()
    while open_set:
        f_cur, current = heappop(open_set)
        if current == goal:
            return reconstruct(parent, goal)
        closed.add(current)
        for nb, w in graph[current]:
            if nb in closed:
                continue
            tentative = g[current] + w
            if tentative < g.get(nb, float("inf")):
                g[nb] = tentative
                parent[nb] = current
                heappush(open_set,
                         (tentative + h[nb], nb))
    return None

04 Frequently Asked Questions

FAQ

What is A* Search?+

What is the time complexity of A* Search?+

The time complexity of A* Search is O(E). Follow the step-by-step visualization to see exactly why.

Where is A* Search used?+

Game pathfinding, robot navigation, route search.

What's a simple analogy for A* Search?+

Expands whichever node has the smallest f, the cost so far g plus an estimate h of what remains. If h never overestimates, the shortest path is guaranteed.

→ Searching — see allRelated

🔍Interpolation Search

O(log log n) avg

🔍Ternary Search