A* Search Algorithm Theory Guide

Rules & Common Mistakes

• Exam Trap: Do Not Stop When the Goal Enters the Open List

  This is the single most common termination mistake in A* exams. The moment students see the Goal node appear in the `openList`, they circle it and call it done. That is wrong — and it will cost you marks every time. A* only guarantees the shortest path when the Goal node is popped from the `openList` and moved into the `closedList`. Until that happens, a cheaper path to the Goal might still be discovered through another route. Wait for the pop, not the discovery.
• Exam Trap: Always Update Existing Nodes in the Open List

  When you expand a neighbour and find it is already sitting in the `openList`, do not skip it. This is where the algorithm does its most important work. Compare your newly calculated $g(n)$ against the $g(n)$ that node currently holds. If your new path is cheaper, cross out the old $f(n)$ score on your paper and write the updated one. If your new path is equal or more expensive, leave it alone. Ignoring this check means you may trace an entire path to the goal using a suboptimal route — and your final answer will be wrong.
• Exam Trap: Nodes in the Closed List Are Permanently Dead — Never Touch Them

  The moment a node moves to the `closedList`, it is finalized. If you later discover what appears to be a cheaper path to a node that is already in the `closedList`, do not recalculate it, do not move it back to the `openList`, and do not update its score. Ignore it completely and move on. With an admissible heuristic, A* guarantees that the first time a node is settled into the `closedList`, the path used to get there is already the optimal one. Revisiting closed nodes is always wasted work — and in an exam context, it signals a fundamental misunderstanding of the algorithm.
• Pro Tip: Two Nodes With the Same $f(n)$ — Do Not Freeze, Just Pick Alphabetically

  Tie-breaking is the moment students stall and waste precious exam time. If two nodes in your `openList` share the exact same $f(n)$ value, A* will find the optimal path regardless of which one you expand first — the final shortest-path cost is guaranteed to be identical either way. The only thing that changes is the order of your trace. To stay consistent with standard grading rubrics, break ties alphabetically. Pick the node whose label comes first in the alphabet, expand it, and keep moving. Do not overthink it.

Strengths, Weaknesses & When To Use It

When to use it:A* is the undisputed standard for pathfinding in the real world — GPS navigation, video game character movement, and robot motion planning all rely on it. On an exam, reach for A* whenever the question gives you a graph with heuristic values and asks for the guaranteed shortest path. If the question does not require the shortest path and just wants any path found quickly, Greedy Best-First Search will get there faster with less work. If the question explicitly constrains memory or asks about space-efficient alternatives, A* is the wrong choice — its memory usage is its critical weakness, and that is exactly what IDA* was designed to fix.

A* Search vs. Greedy Best-First Search

A* and Greedy Best-First Search both use a heuristic $h(n)$ to steer toward the goal — but they have radically different philosophies about what that means. Greedy is short-sighted: it only cares about which node looks closest to the goal right now, with no memory of how expensive it was to get there. A* is balanced: it weighs the real cost of the journey so far against the estimated cost remaining. A* is not a different algorithm from Greedy — it is Greedy Search that learned to remember the past.

• The Formula: Greedy Search evaluates nodes using only $f(n) = h(n)$ — it looks exclusively at the estimated future cost and asks 'which node appears closest to the goal?' A* evaluates nodes using $f(n) = g(n) + h(n)$ — it combines the exact past cost with the estimated future cost and asks 'what is the true total cost of this entire journey?' One number versus two is the entire difference between reckless and reliable.
• The Mindset — Taking the Bait: Greedy blindly chases whichever node has the smallest $h(n)$, even if reaching that node required crossing a brutally expensive edge. It sees a node that looks close to the goal and sprints toward it, ignoring the cost of the road it just crossed. A* cannot be baited this way — the $g(n)$ term penalizes expensive paths regardless of how close they appear to the goal. An attractively-positioned but expensively-reached node will always lose out to a cheaper, well-rounded alternative.
• The Optimality Guarantee: A* with an admissible heuristic is mathematically guaranteed to find the shortest path every time. Greedy Search carries no such guarantee — it frequently returns a suboptimal path because it commits to whatever looks promising early and never reconsiders. A node that appeared slightly further away but offered a far cheaper overall route gets ignored entirely. Greedy is fast. Greedy is also frequently wrong.
• What Your Exam Is Actually Testing: When a professor asks you to trace both algorithms on the same graph, that graph has been deliberately designed with a trap — a visually attractive path that is actually more expensive than the optimal route. They are testing whether you know that Greedy will take the bait, follow the low $h(n)$ values straight into an expensive dead end, and return a suboptimal answer. A* will calculate $g(n)$ at every step, reject the expensive shortcut, and find the true shortest path. If your Greedy and A* traces return the same path on an exam question, re-check your work — the question was almost certainly designed so they diverge.

Implementation Pseudocode

// A* maintains two lists throughout the entire search
// openList  = nodes discovered but not yet finalized — sorted by f(n) = g(n) + h(n)
// closedList = nodes fully processed — their shortest path is guaranteed and locked in

function aStar(startNode, goalNode):

    // ── INITIALIZATION ──────────────────────────────────────────────────

    // Set the start node's g(n) to 0 — no travel cost yet
    // Every other node's g(n) starts at Infinity (undiscovered)
    startNode.g = 0
    startNode.h = heuristic(startNode, goalNode)
    startNode.f = startNode.g + startNode.h

    // Add the start node to the openList as the first candidate
    openList  = [startNode]
    closedList = []


    // ── MAIN LOOP ────────────────────────────────────────────────────────

    while openList is not empty:

        // Always pop the node with the lowest f(n) value
        // This is what makes A* informed — it always chases the most promising path
        current = node in openList with the lowest f(n)
        remove current from openList

        // EXAM TRAP — Goal check happens HERE, after popping, not when generating neighbours
        // Checking on discovery would not guarantee the shortest path had been found yet
        if current == goalNode:
            return reconstruct_path(current)  // trace parent pointers back to start

        // Move current to the closedList — its shortest path is now finalized
        add current to closedList


        // ── EXPAND NEIGHBOURS ───────────────────────────────────────────

        for each neighbour in getNeighbours(current):

            // EXAM TRAP — Nodes in the closedList are permanently dead
            // A* with an admissible heuristic guarantees their path was already optimal
            // Do not recalculate, do not re-add, do not touch them
            if neighbour is in closedList:
                continue

            // Calculate the g(n) cost to reach this neighbour via current
            tentative_g = current.g + edgeCost(current, neighbour)

            if neighbour is not in openList:

                // Newly discovered node — calculate all three values and add it
                neighbour.g = tentative_g
                neighbour.h = heuristic(neighbour, goalNode)
                neighbour.f = neighbour.g + neighbour.h
                neighbour.parent = current
                add neighbour to openList

            // EXAM TRAP — Only update if the new path is strictly cheaper
            // Equal or more expensive paths are discarded — the existing entry stays
            else if tentative_g < neighbour.g:

                // Found a cheaper route to a node already in the openList
                // Cross out its old scores and overwrite with the improved values
                neighbour.g = tentative_g
                neighbour.f = neighbour.g + neighbour.h
                neighbour.parent = current

    // openList is empty and goal was never popped — no path exists
    return failure


// ── INITIAL CALL ─────────────────────────────────────────────────────
// aStar(startNode, goalNode)

Time & Space Complexity

A* Exam Questions Students Always Get Wrong

• Why can't I stop the algorithm the second the Goal node appears in my openList?

  Because appearing in the `openList` only means the goal has been discovered — not that the cheapest path to it has been found yet. A cheaper route to the goal might still be sitting undiscovered in another part of the graph, waiting to be expanded. You must wait until the goal node is popped from the `openList` — meaning it has the lowest $f(n)$ of all remaining candidates — before terminating. Stopping on discovery is the single most common reason students lose marks on A* trace questions.

• What exactly happens if my heuristic overestimates the true distance to the goal?

  The admissibility guarantee breaks immediately, and A* is no longer guaranteed to return the shortest path. An overestimating $h(n)$ inflates the $f(n)$ score of certain nodes, causing A* to avoid exploring them — even if they sit on the true optimal route. The algorithm may confidently return a suboptimal path with no indication that anything went wrong. On an exam, if asked to justify why a heuristic is valid, you must state that it never overestimates — that is the definition of admissibility.

• I found a new path to a node already in my openList, but the new $g(n)$ is higher. Do I update it?

  No — leave it completely untouched. You only ever update an existing `openList` node if the newly calculated $g(n)$ is strictly lower than the value it currently holds, meaning you found a genuinely cheaper route. If the new $g(n)$ is equal or higher, the existing entry is already better and the new path is irrelevant. Overwriting with an equal or worse score is a marking error that cascades into every downstream calculation.

• What if two nodes in the openList have the exact same $f(n)$ score? Which one do I pop first?

  Mathematically, it does not matter — A* will find the same optimal path cost regardless of which tied node you expand first. The final answer is guaranteed to be identical either way. On an exam, however, always break ties alphabetically — choose node A before node B, B before C, and so on. This keeps your trace consistent with the expected output on your professor's grading rubric and eliminates any ambiguity in your working.

• My professor gave a graph where $h(n) = 0$ for every single node. Is this a trick question?

  It is not a trick — it is a test of whether you understand what the heuristic actually does. When $h(n) = 0$ everywhere, A* loses all directional guidance and makes every decision based purely on $g(n)$, the exact cost so far. This means A* degrades exactly into Dijkstra's algorithm, expanding nodes in order of their true distance from the start with no goal-seeking behaviour at all. Trace it normally, and if your exam asks you to comment on it, write: with $h(n) = 0$, A* becomes an uninformed search equivalent to Uniform Cost Search.