I've been looking for the proof of correctness for the A star (A*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A* algorithm. I'm looking for a proof that if the heuristic is admissible, A* will always give an optimal path.

Please help me understand.

To clarify, I want a proof that the path found by A* is correct (i.e., is the cheapest/shortest path to the destination), not a proof that the A* algorithm is optimal (i.e., that any other algorithm that uses the same heuristic will expand at least as many nodes as A*). Also, I'm looking for a proof that only uses the assumption that the heuristic is admissible (without assuming that the heuristic is monotonic or consistent). I've looked in CLRS and haven't found any such proof.

  • $\begingroup$ See if this question helps: stackoverflow.com/questions/10195780/…. $\endgroup$ Mar 13, 2016 at 16:29
  • $\begingroup$ @YuvalFilmus In the answer, it's given that the heuristic needs to be monotonic. But if that is always true, then A* algorithm would never make any incorrect choices and any node that it expands would definitely have to be on the optimal path to the terminal vertex. As can be seen in this visualization, that does not happen. upload.wikimedia.org/wikipedia/commons/5/5d/… Where am I going wrong? $\endgroup$ Mar 13, 2016 at 16:56
  • $\begingroup$ Monotonicity is the difference between admissible heuristic and consistent heuristic (Wikipedia terminology). Apparently it's enough for the heuristic to be admissible. The proof of correctness is probably a simple exercise, which is why you don't see it so often. $\endgroup$ Mar 13, 2016 at 17:05
  • $\begingroup$ I was wondering if cs.stackexchange.com/questions/44926/… actually addresses your question or not. In case it does not, what is missing there? (so that we can extend that answer to deal with your concerns) $\endgroup$ Mar 14, 2016 at 7:39
  • $\begingroup$ My doubt is regarding why the path chosen by A* is correct, i.e., it is the shortest path. At each iteration, A* expands a node with minimum f() as in the explanation there, but the distance from the source or initial terminal that we have estimated for it at this point in time need not be correct. How then can we say, that our algorithm will eventually give the correct shortest path? I am thinking along the lines of the proof for Djikstra's algorithm right now where we show that the estimated distance of the node being expanded is same as the actual distance from the source. $\endgroup$ Mar 14, 2016 at 17:54

1 Answer 1


Check the original paper which talks about its correctness -

Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems Science and Cybernetics, IEEE Transactions on 4.2 (1968): 100-107.

See especially Section II and Theorem 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.