Keep accumulated and estimated cost separate
A* prioritizes a candidate vertex v using f(v)=g(v)+h(v), where g is the best path cost discovered from the source and h estimates the remaining cost to a goal. Here the setting is a finite graph with nonnegative edge weights. Setting every h to zero recovers Dijkstra-style priorities. An estimate is not a replacement for the actual accumulated cost. Similarly, discovering a goal as a neighbor is different from taking it from the priority queue under the algorithm’s proper termination condition. The distinction affects which path can safely be reported.
Compare two candidate branches
Let S→A cost 2, S→B cost 4, A→G cost 5 and B→G cost 1. With h(A)=5 and h(B)=1, the candidates have priorities 7 and 5, so the search favors B and finds a goal route costing 5. With zero estimates, A may be expanded earlier, but the correct final minimum is unchanged. If h(B) is instead an overestimate of 100, the cheaper branch can be deferred while a cost-7 goal is selected. Guidance can save exploration only under conditions compatible with the desired correctness guarantee.
Distinguish admissibility from consistency
An admissible heuristic never exceeds the true remaining optimal cost. Consistency additionally requires h(u)≤w(u,v)+h(v) for every edge and a zero estimate at a goal. A consistent heuristic supports the standard argument that a vertex removed with its best priority can be finalized. With an admissible but inconsistent heuristic, a better g may require reopening a vertex already considered closed. Do not attach an admissibility-only optimality claim to a graph-search implementation that permanently discards such later improvements. The algorithm and its assumptions must be described together.
Useful guidance is not free
A helpful estimate can reduce expansions, but does not promise that every instance will be faster than Dijkstra’s algorithm. Include the cost of evaluating h, maintaining visited states and ignoring outdated queue entries. On a four-neighbor unit-cost grid, Manhattan distance is a lower bound obtained by ignoring obstacles. Adding diagonal moves or changing move costs requires reevaluating that bound. Infinite state spaces require additional completeness conditions beyond this finite-graph discussion. Benchmark expanded states and memory as well as elapsed time, and verify path cost against a known-correct baseline before interpreting a speed improvement.