Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

The A* Algorithm is the optimal (provided the heuristic function is underestimated), complete & admissible (provided some conditions). I know the proofs of admissibility & optimality.

But how do you prove that the A* Algorithm is complete?

share|improve this question
interesting factoid if the heuristic function is set to h(x)=0 you get dijkstra – ratchet freak Mar 17 '13 at 17:32
yeah, it is. +1 to the point. Thanks. – vintesh Mar 17 '13 at 18:17

1 Answer 1

up vote 6 down vote accepted

For a proof of completeness, it is not necessary to look specificially at A*. Any finite graph search algorithm using a node queue where you take one element off, generate all children of that graph node and put them back into the queue is complete, "A*" is just a special case of that kind of algorithms.

Once you got this, it is easy to find a proof of completeness for arbitary graph search by Google, for example, this one:

The proof itself is not very complex, but IMHO still too long for summarizing it here.

share|improve this answer
Thanks. Got the concept. Working on the link provided. – vintesh Mar 17 '13 at 18:08
Meh, summarizing a graph search is easy enough. Super-brief proof by contradiction: Given an algorithm as described above: Let G be the smallest graph for which the algorithm fails. By construction (this step is easier if you define your algorithm recursively, but I'm summarizing, so I'll handwave instead), the algorithm eventually reaches a state where: A) It has discovered a path from START to PEN, where PEN is a node with an edge directed towards END and B) END is in the node queue (or was in it previously). So, it succeeded. Contradiction. – Brian Oct 19 at 18:25
To clarify: We know it found a path from START to PEN because START to PEN is smaller than the smallest graph for which the algorithm fails. – Brian Oct 19 at 18:26
Alternatively, a proof by induction: We can find a path from START to one edge away from start (or from START to START, if you want a one node graph). Any existing graph can be build by adding new edges to this two-node graph, one by one, without making the graph unsolveable. – Brian Oct 19 at 18:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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