Algorytm A* – algorytm heurystyczny znajdowania najkrótszej ścieżki w grafie ważonym z dowolnego wierzchołka do wierzchołka spełniającego określony warunek zwany testem celu. Algorytm jest zupełny i optymalny, w tym sensie, że znajduje ścieżkę, jeśli tylko taka istnieje, i przy tym jest to ścieżka najkrótsza. Stosowany głównie w dziedzinie sztucznej inteligencji do rozwiązywania problemów i w grach komputerowych do imitowania inteligentnego zachowania.
Algorytm został opisany pierwotnie w 1968 roku przez Petera Harta, Nilsa Nilssona oraz Bertrama Raphaela. W ich pracy naukowej został nazwany algorytmem A. Ponieważ jego użycie daje optymalne zachowanie dla danej heurystyki, nazwano go A*.
Działanie algorytmu Algorytm A* od wierzchołka początkowego tworzy ścieżkę, za każdym razem wybierając wierzchołek z dostępnych w danym kroku niezbadanych wierzchołków tak, by minimalizować funkcję zdefiniowaną:
gdzie: – droga pomiędzy wierzchołkiem początkowym a Dokładniej: suma wag krawędzi, które należą już do ścieżki plus waga krawędzi łączącej aktualny węzeł z – przewidywana przez heurystykę droga od do wierzchołka docelowego.
W każdym kroku algorytm dołącza do ścieżki wierzchołek o najniższym współczynniku Kończy w momencie natrafienia na wierzchołek będący wierzchołkiem docelowym.