Wait, What?
A* can be exactly Dijkstra’s algorithm—or dramatically faster—depending on one extra function that never walks an edge.
Heuristic search looks almost magical the first time you see it. Dijkstra’s algorithm expands states according to cost already paid. A* adds an estimate of the cost still remaining and asks a more useful question: which unfinished route currently looks cheapest from start all the way to goal?
The professional lesson is not “A* is faster.” A* is a framework whose behaviour depends on the quality and mathematical properties of the heuristic, the graph representation, the priority-queue discipline, duplicate-state handling, memory budget and the operational objective.
Quick Answer
Learn heuristic search through the route weighted shortest paths → Dijkstra → goal-directed search → g(n), h(n), f(n) → admissibility → consistency → open/closed sets → relaxation and re-opening → heuristic design → tie-breaking → weighted A* → memory pressure → IDA* and bounded-memory variants → production validation. A beginner should be able to trace a small grid by hand. A professional should be able to state the guarantee being claimed, prove the heuristic property that supports it, instrument node expansions and memory, and decide when exact optimality is worth its cost.
1. Start With the Problem A* Is Trying to Improve
Suppose a weighted graph has a start vertex and one particular goal. Dijkstra’s algorithm is excellent when we need shortest distances broadly, but it has no notion of direction toward a designated goal. If many frontier vertices have similar path cost, it may explore large regions that are mathematically relevant yet practically unhelpful for this one query.
2. Separate Cost Already Paid From Cost Still Estimated
For a state n, A* commonly uses f(n) = g(n) + h(n). Here g(n) is the best known cost from the start to n, while h(n) estimates the cheapest remaining cost from n to the goal. The priority queue chooses a state with the smallest current f-value.
The learner should say these meanings aloud before touching code. Confusing g and h causes nearly every later proof to become foggy.
3. Zero Heuristic Gives You Dijkstra
If h(n)=0 for every state, then f(n)=g(n) and A* reduces to Dijkstra-style ordering. This is a powerful sanity check: A* is not a mysterious unrelated algorithm. It is a goal-directed extension of lowest-cost-first search.
Stanford’s current A* notes make this relationship explicit and show how the heuristic focuses the search toward a target. See Stanford CS106B: Dijkstra and A*.
4. A Heuristic Is a Claim About the Remaining Problem
A heuristic is not merely a convenient number. It is a lower-bound, estimate or guidance signal derived from problem structure. Straight-line distance can guide road search because any real road route must normally be at least as long as the geometric lower bound under a compatible cost model.
5. Admissibility Protects Optimality
A heuristic is admissible when it never overestimates the true cheapest remaining cost. Under the standard assumptions, this optimism supports A*’s optimality guarantee. The practical habit is to ask: what evidence makes this estimate a lower bound?
A concise classical statement is available in MIT 6.034: Admissible Search Algorithms.
6. Consistency Is Stronger and Operationally Convenient
A consistent (monotone) heuristic respects a triangle-like condition along every edge: the estimated cost at a state should not exceed the edge cost plus the estimate at the neighbour. Consistency implies admissibility in the standard setting and helps ensure that f-values do not decrease along a path.
Cornell’s A* recitation explains both admissibility and monotonicity and relates consistent A* to a reweighted Dijkstra search. See Cornell CS312: A* Search.
7. Trace the Frontier Before You Implement It
Give learners a 5×5 grid, a start, a goal, a few blocked cells and unit edge costs. Write g, h and f beside every expanded cell. After each step, ask which state is in the frontier, which state leaves the frontier next, and which predecessor pointer changes.
8. The Priority Queue Is Part of the Algorithm
A* repeatedly needs the frontier state with the smallest priority. In practice this normally means a heap or specialised priority queue. The implementation must also decide how to handle a state whose priority improves after it is already present in the queue: decrease-key, duplicate entries plus stale-entry checks, or another controlled strategy.
9. Relaxation Still Matters
The heuristic changes search order, not the underlying need to maintain best-known path costs. If a cheaper route to a neighbour is found, update its g-value and predecessor. A learner who can recite f=g+h but cannot explain relaxation has not yet understood A*.
10. Open and Closed Sets Are Bookkeeping, Not the Core Idea
Many presentations use an open set for discovered frontier states and a closed set for expanded states. These names are useful, but the deeper questions are whether a state may be expanded more than once, under what heuristic assumptions re-opening is necessary, and how stale queue entries are detected.
11. Inconsistent Heuristics Change Duplicate-State Handling
With an inconsistent heuristic, a better path can be discovered to a state that was previously expanded. A graph-search implementation may therefore need to re-open states. The safe professional rule is to connect implementation shortcuts directly to the theorem assumptions that justify them.
12. Design Heuristics From Relaxed Problems
One reliable heuristic-design technique is to remove constraints from the original problem, solve the easier relaxed problem, and use its optimal cost as a lower bound. If the relaxation really cannot cost more than the original, the resulting value is naturally optimistic.
13. Dominating Heuristics Can Reduce Search
If two admissible heuristics are available and one is always at least as large as the other while remaining admissible, the stronger heuristic generally carries more information. But computing it may cost more. Measure total work, not just number of expanded nodes.
14. Heuristic Computation Has a Price
A heuristic that saves 90% of expansions but takes milliseconds per state can lose to a cheaper heuristic on small or highly regular problems. Professional evaluation therefore separates search work from heuristic work and measures end-to-end latency.
15. Tie-Breaking Can Matter Even When Correctness Does Not
Many frontier states may share the same f-value. Tie-breaking on larger g, smaller h, insertion order or another stable key can change the explored region and memory pattern while preserving the same formal guarantee under the same assumptions.
16. Weighted A* Makes the Trade-Off Explicit
A common variant uses f(n)=g(n)+w·h(n) with w>1. This pushes the search more strongly toward the goal and often reduces search effort, but exact optimality may be weakened. The lesson is valuable far beyond A*: production algorithms often expose a controlled quality–cost trade-off rather than pretending one operating point is universally best.
17. Memory Is Often A*’s Real Bottleneck
A* can retain a large frontier plus records for discovered states. On enormous state spaces, memory can fail before arithmetic becomes expensive. That is why iterative-deepening A* (IDA*), recursive best-first search and other memory-bounded methods matter.
18. IDA* Trades Re-Expansion for Lower Memory
IDA* performs depth-first searches under increasing f-cost thresholds. It can use dramatically less memory than ordinary A*, but it may regenerate states many times. The right comparison is therefore not “which algorithm is faster?” but “which resource constraint dominates this workload?”
19. Domain Structure Can Beat Generic A*
Road routing, robotics, game maps and planning systems often add preprocessing, landmarks, hierarchical representations or domain-specific lower bounds. Microsoft Research’s ALT work combines A* with landmarks and triangle-inequality lower bounds to accelerate shortest-path queries on large graphs.
See Computing the Shortest Path: A* Search Meets Graph Theory.
20. A* Is Also a Lesson in Model Quality
A brilliant search algorithm cannot repair a wrong cost function. If edges measure geographic distance but the real objective is travel time, the shortest returned path can be perfectly optimal for the wrong question. Model the objective before tuning the search.
21. Build a Correctness Test Harness
- Compare A* against Dijkstra on random non-negative weighted graphs when the heuristic is admissible.
- Use h=0 as a baseline equivalence test.
- Test start=goal, disconnected graphs, single-edge graphs and graphs with many equal-cost paths.
- Deliberately inject an overestimating heuristic and observe which guarantee disappears.
- Verify every returned path uses real edges and recompute its cost independently.
22. Measure Search Shape, Not Only Runtime
Record expanded states, generated states, maximum frontier size, duplicate detections, re-openings, heuristic calls and final path cost. Two implementations with similar latency can have very different scaling behaviour.
23. Common Learning Failure States
- Treating the heuristic as a guess with no mathematical obligation.
- Assuming admissible and consistent mean the same thing.
- Stopping at the first discovered goal rather than the correct termination condition.
- Forgetting relaxation because the heuristic feels like the main idea.
- Using Euclidean or Manhattan distance without checking whether it is a lower bound under the actual movement costs.
- Marking states permanently closed even when the chosen heuristic/implementation permits a later improvement.
- Claiming A* is always faster than Dijkstra.
- Ignoring memory growth.
- Benchmarking only one friendly map.
- Optimising node expansions while ignoring heuristic-computation cost.
24. A Beginner-to-Professional Learning Ladder
- Level 1: trace BFS and Dijkstra on a tiny graph.
- Level 2: compute g, h and f values by hand.
- Level 3: implement A* with a priority queue and predecessor map.
- Level 4: prove or disprove admissibility for a proposed heuristic.
- Level 5: distinguish admissibility from consistency.
- Level 6: implement safe duplicate handling and test against Dijkstra.
- Level 7: design heuristics from relaxed problems.
- Level 8: explore weighted and memory-bounded variants.
- Level 9: benchmark expansions, memory and heuristic cost separately.
- Level 10: choose search architecture for a real workload with explicit quality and latency constraints.
25. Teach It by Prediction Before Production
A novice should first predict which frontier state A* will expand, then run a small visual trace, investigate why that state won, modify the heuristic, and finally implement the search. This follows the Predict–Run–Investigate–Modify–Make progression used in PRIMM.
See Raspberry Pi Foundation: PRIMM.
26. Use Worked Examples With Named Subgoals
Label the procedure explicitly: initialise frontier; remove best candidate; test/expand; relax neighbours; update predecessor; update priority; reconstruct path. Research on subgoal-labelled worked examples in introductory programming found benefits for problem solving and course outcomes.
See Margulieux, Morrison & Decker: Subgoal-labelled Worked Examples.
27. Fade the Scaffolding
First provide every g, h, f and queue state. Next hide selected values. Then provide only the graph and heuristic. Finally ask the learner to design a heuristic and justify its guarantee. Faded worked examples move responsibility toward the learner without dropping them into an empty editor too early.
28. Visualisation Should Drive Explanation
Animation is useful when it makes the frontier, closed set and direction of search visible, but the learner should still explain why a state is expanded. Recent classroom research on algorithm visualisation found motivational and behavioural benefits, while overall performance effects depended on learner proficiency and conditions.
See Fu et al. (2025): Effects of Algorithm Visualisation.
29. Internal Connections
Use the existing Graph Algorithms article for representation, BFS, DFS and shortest-path foundations, and Algorithm Correctness Proofs for the proof habits behind guarantees. This article owns the distinct job of heuristic, goal-directed search and its quality–memory trade-offs.
30. Professional Direction
Advanced study includes bidirectional A*, landmark heuristics, pattern databases, contraction hierarchies, anytime repairable A*, weighted and focal search, dynamic replanning, D* variants, multi-agent path finding, robot motion planning and heuristic learning. The unifying professional question remains the same: what information guides the search, what guarantee does that information preserve, and what resource does the system spend to obtain it?
31. Complexity Depends on the Search Space and the Heuristic
A* does not have one practical runtime independent of the problem. With a weak heuristic it can behave much like Dijkstra. In implicit state spaces its work is often discussed through branching factor and solution depth; in explicit graphs, priority-queue operations, edge relaxations and the number of expanded states matter. Memory can scale with the number of discovered states. A professional report should therefore state the representation, frontier data structure, duplicate policy and heuristic—not just a Big-O expression detached from the workload.
32. Heuristic Correctness Needs Property-Based Tests
Generate many small solvable instances whose exact optimal costs can be obtained by Dijkstra or exhaustive search. For every state sampled from those instances, compare h(n) with the true remaining cost to test admissibility. For every directed edge, test the consistency inequality under the chosen cost model. Property-based testing is especially useful because a heuristic can appear correct on visual examples while failing on one awkward movement rule, diagonal cost or terrain exception.
33. Separate Algorithm Error From Model Error
If A* returns an unexpected route, investigate in order: Are edge costs correct? Is the graph connected as intended? Is the heuristic measured in the same units as path cost? Is the heuristic valid for one-way edges, teleportation or terrain multipliers? Is the queue discarding a better duplicate? Is the termination rule justified? This layered debugging method stops developers from “fixing” the search algorithm when the real defect is data or modelling.
34. A Professional Exercise: Build an Anytime Search Dashboard
Run the same map with h=0, an admissible geometric heuristic, a stronger admissible heuristic and weighted A*. Plot path cost, expanded states, maximum frontier, heuristic time and end-to-end latency. Then impose a hard time or memory budget and ask which variant should ship. The exercise turns algorithm analysis into an engineering decision rather than a race to one benchmark number.
35. Final Learning Check
Without notes, explain why h=0 recovers Dijkstra, give an admissible but weak heuristic, distinguish admissibility from consistency, describe when a state may need reopening, and name one reason A* can fail operationally despite being mathematically correct. If any answer is vague, return to a hand trace before adding more optimisation.
eduKate Sengkang 