Spełnienie tego warunku gwarantuje poprawność decyzji podejmowanych przez algorytm w oparciu o heurystykę, ponieważ nie zajdzie sytuacja, w której dla pewnego będzie większe niż faktyczna długość ścieżki z do wierzchołka docelowego. Niespełnienie warunku oznacza, że algorytm mógłby wskazać nieoptymalną ścieżkę, jeśli dla pewnego węzła w optymalnej ścieżce byłoby zawyżone.
Algorytm A* jest optymalny dla danej heurystyki, co znaczy, że nie istnieje inny algorytm, który z pomocą tej samej heurystyki odwiedziłby mniej wierzchołków niż A*.
Przypadki graniczne Istnieją bardziej znane algorytmy grafowe, które można sprowadzić do algorytmu A* przy charakterystycznym grafie lub charakterystyczną heurystyką: przeszukiwanie w głąb przeszukiwanie wszerz algorytm Dijkstry –
Dlaczego A* jest dopuszczalny oraz optymalny obliczeniowo? Zakładając, że używana w algorytmie heurystyka jest dopuszczalna, możemy stwierdzić, iż A* jest dopuszczalny (ang. admissible). Oznacza to, że zawsze poda nam prawidłowe rozwiązanie, jeżeli takowe istnieje. Co więcej, algorytm ten podczas działania przeszukuje mniej węzłów niż jakikolwiek inny dopuszczalny algorytm przeszukiwania z taką samą heurystyką.