A* używa f(n) = g(n) + h(n). Jeśli heurystyka h jest dopuszczalna (nie przeszacowuje) i spójna, A* jest optymalny i odwiedza mniej węzłów niż Dijkstra. Gdy h przeszacowuje, optymalność nie jest gwarantowana. Dla h = 0 A* redukuje się do Dijkstry.