Među svim algoritmima pretraživanja grafova A* algoritam pronalazi cilj najbrže. Algoritam A* uz određene predpostavke objezbeđuje otvaranje najmanjeg broja čvorova uz nalaženje rješavajućeg puta minimalne cijene. Zato ga ponekad nazivaju optimalnim algoritmom.

Ime metoda se izgovara "A star" ili "A zvijezda", a autori (Peter Hart, Nils Nilsson i Bertram Raphael) su mu dali jer je nastao na osnovu ranijeg A1 algoritma, proširujući njegove mogućnosti i ostavljajući mogućnost proširenja na sve nove verzije (zato * da obuhvati sve buduće verzije i brojeve).

Pretraga se vrši tako što se kreće od početnog čvora i na svakom koraku sa lista raspoloživih čvorova bira se onaj čvor u kojem funkcija f ima najmanju vrijednost.

Na početku pretraživanja u početnom čvoru s, funkcija f(s) ima vrijednost f(s)=0+h(s)=h(s). g(s)=0, jer je dužina puta 0.  Ako je procjena funkcije h tačna, onda funkcija f ne mijenja svoju vrijednost u toku čitavog procesa pretraživanja sve do završnog čvora.
U toku pretraživanja pri prelasku na nove čvorove raste cijena puta g(n), ali se zato smanjuje procjenjena cijena h(n) do završnog čvora.
Ako funkcija h ne daje tačne procjene, onda u toku pretraživanja funkcija f može da mijenja vrijednosti
Funkcija g se koristi u slučaju da funkcija h nije dobro odabrana, kada g preuzima dalje usmjeravanje pretrage.

Može se pokazati da je pretraživanje ovim algoritmom optimalno, tj. nalazi se optimalan rejšavajući put, ako funkcija h uvijek daje tačne procjene.

A* algoritam koristi OPEN listu na koju sprema one čvorove koji se mogu proširiti na svoje sljedbenike, krenuvši od startnog čvora.

Čvor s najmanjom vrijednošću funkcije f skida se s OPEN liste i proširuje njegovim sljedbenicima koji dolaze na OPEN listu. Svaki novi čvor koji dolazi na listu sadrži pokazivač na čvor kojeg je naslijedio. Budući da se s liste uvijek skida onaj čvor s najmanjom vrijednošću funkcije f, pretraživanje će biti fokusirano što bržem pronalaženju cilja. Algoritam je završen kada se na listi pojavi cilj, a optimalni je put određen praćenjem pokazivača na prethodni čvor krenuvši od cilja.

Slijedeći bilo koji put na stablu čvorova od korijena čvora, vrijednost funkcije f nikada se ne smanjuje. To je svojstvo ispunjeno samo ako je heuristička funkcija monotona. Može se pokazati da je heuristička funkcija monotona ako i samo ako posjeduje svojstvo nejednakosti trokuta (što zadovoljava euklidska udaljenost). U slučaju nenalaženja puta zbog zakrčenosti prostora preprekama između starta i cilja, algoritam će završiti s praznom listom.