Search Algorithms
Informed search

Weighted A*

Turn a speed dial: trade a little optimality for a lot of speed.

Final path found by Weighted A*
On the Sydney → London problem, Weighted A* finds: Sydney → Colombo → Istanbul → London — total 23.5h.
▶ Watch Weighted A* run

The idea

Weighted A* is A* with a "greediness dial." It uses f(n) = g(n) + w*h(n), where w is a weight bigger than 1 that exaggerates the estimate of remaining distance to the goal. This makes the search rush toward the goal faster, expanding fewer nodes, at the cost of possibly finding a path that isn't the shortest. The bigger w is, the faster and greedier it gets.

How it works

  1. Pick a weight w greater than 1. This is your dial: 1 = careful A*, very large = reckless Greedy.
  2. Put the start node in OPEN (the frontier of nodes waiting to be explored). Give it g = 0 and score f = 0 + w*h(start).
  3. Take the node with the smallest f out of OPEN. This is the node that looks most promising toward the goal.
  4. If it is the goal, stop and rebuild the path by following parent links backward.
  5. Otherwise move that node into CLOSED (already-expanded nodes) so we never redo it.
  6. For each neighbor, compute a tentative g = (current node's g) + edge cost.
  7. If that neighbor is new, or we just found a cheaper g for it, record its parent, store g, set f = g + w*h(neighbor), and put it in OPEN.
  8. Repeat: keep pulling the smallest-f node from OPEN until you reach the goal or OPEN is empty (no path).

See it step by step

Watch Weighted A* search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Weighted A* step
Start at Sydney. OPEN (the frontier) holds just Sydney.
Expanding
OPEN — frontier
CLOSED — traversal
Path so far
Cost so far
Step 1 / 5

OPEN, CLOSED & the data structures

OPEN is a priority queue: it always hands back the node with the smallest f = g + w*h, so the most goal-promising node gets explored next. CLOSED is a set of nodes we've already expanded, used to avoid re-processing the same node and getting stuck in loops. Each node also remembers its best-known g cost and its parent so we can trace the final path back from the goal.

Pseudocode

function WeightedAStar(start, goal, w):   # w > 1
    OPEN = priority queue ordered by f
    g[start] = 0
    f[start] = 0 + w * h(start)
    add start to OPEN
    CLOSED = empty set

    while OPEN not empty:
        n = node in OPEN with smallest f
        remove n from OPEN
        if n == goal:
            return reconstruct_path(n)
        add n to CLOSED

        for each neighbor m of n:
            if m in CLOSED: continue
            tentative_g = g[n] + cost(n, m)
            if m not seen or tentative_g < g[m]:
                parent[m] = n
                g[m] = tentative_g
                f[m] = g[m] + w * h(m)   # weight only on h
                add/update m in OPEN
    return failure   # OPEN empty, no path

At a glance

Complete?Yes — if a solution exists it will be found, since it still explores OPEN systematically until the goal or an empty frontier.
Optimal?No — it trades optimality for speed; the path found costs at most w times the true optimal cost (this is called w-admissible).
TimeO(b^d)-style exponential in the worst case, but in practice much faster than A* — a larger w expands fewer nodes and reaches the goal sooner.
SpaceO(number of nodes stored), since every node kept in OPEN and CLOSED lives in memory — the main practical limit, though often smaller than A* because fewer nodes are expanded.

👍 When to use it

  • You need an answer fast and a slightly-longer path is acceptable (robots, games, big maps).
  • Plain A* is too slow or runs out of memory because it expands too many nodes.
  • You want a tunable knob to trade solution quality for speed by adjusting w.
  • You have a bounded guarantee requirement: 'within w times optimal' is good enough.

⚠️ Watch out for

  • The weight goes ONLY on h, not on g. f = g + w*h. Weighting g too breaks the meaning.
  • Bigger w = faster but worse paths; w must stay above 1 (w = 1 is just plain A*, w -> infinity approaches Greedy Best-First).
  • The result is not the shortest path — never claim optimality; only claim 'at most w times optimal'.
  • If h is not admissible (it overestimates), the w-times-optimal guarantee no longer holds.

Now see it for yourself

Open Weighted A* in the visualizer — step through it, pause, and watch OPEN & CLOSED change.

▶ Watch it run