An admissible heuristic estimates the cost from a node to a goal without exceeding the true minimum remaining cost. In route finding, straight-line distance to the destination is a candidate estimate: it helps prioritize promising roads without claiming that a winding route is shorter than a direct line. The estimate must be a lower bound for every node, not just for the starting point. section 4.3.3
A* ranks a node using f(n) = g(n) + h(n): the cost already incurred, g(n), plus the estimated cost still to go, h(n). Setting h(n) to zero everywhere removes that guidance, making A* behave like uniform-cost search. A lower bound closer to the true remaining cost can improve search time; a weak bound leaves more work to do. section 4.3.3
Figure 4.22 The A* steps to find the shortest path between the source node S and goal node G in an 8 POIs road network. The sum of the already incurred costs and the distance to the goal is used as the heuristic value to determine whether to expand a certain node.
The eight-point road network traces how A* uses incurred cost and estimated distance to the goal when choosing nodes to expand. section 4.3.3
To try this on a weighted graph, provide an A* routine with a heuristic function and an edge-cost function. Track the best known cost from the origin, then compare frontier nodes by that cost plus their estimated cost to the destination. The Python routing example uses NetworkX, optalgotools nodes and a configurable heuristic; its small graph is a place to inspect expansion choices before tackling larger networks. section 4.3.3
Keep admissibility distinct from making the heuristic more influential. Weighted A* multiplies h(n) by a weight; choosing a weight above one gives the estimate more influence, but the weighted estimate should not automatically be treated as the same lower bound. At country-scale routing, hierarchical approaches instead use abstractions and admissible heuristics to prune a search space that basic routing methods cannot explore quickly enough for interactive use. section 4.3.3 section 4.3.4
