Algorithmshard

A* search: how does the heuristic affect optimality?

Answer

A* uses f(n) = g(n) + h(n). If the heuristic h is admissible (never overestimates) and consistent, A* is optimal and explores fewer nodes than Dijkstra. If h overestimates, optimality is not guaranteed. With h = 0, A* reduces to Dijkstra.

Related questions

Algorithms

Bellman–Ford: when do you use it and what extra capability does it have over Dijkstra?

#bellman-ford#shortest-path#graphs

Algorithms

What does the Floyd–Warshall algorithm compute and what is its complexity?

#graphs#shortest-path#floyd-warshall

Algorithms

Kruskal vs Prim for MST — how do they differ?

#mst#kruskal#prim

Algorithms

A* vs Dijkstra — what’s the difference and when is A* faster?

#a-star#dijkstra#heuristics

Algorithms

Why doesn’t Dijkstra work with negative edge weights, and what can you use instead?

#dijkstra#bellman-ford#negative-weights

Algorithms

When can BFS replace Dijkstra’s algorithm?

#shortest-path#bfs#dijkstra