# Consistent heuristic and A*

The following graph has consistent heuristic.

An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be found before AC?

• Why do you think that? Have you tried running A* by hand to see what it does? – D.W. May 9 '18 at 3:26
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael May 9 '18 at 8:35
• @BlueRaja-DannyPflughoeft By definition consistent heuristic is, when h(n) <= c(n,n')+h(n').. In this case 5 <= 1+8, which is true, so its not overestimated. – toto8080 May 9 '18 at 9:12
• I don't understand your question: A* doesn't guess paths. Look up the pseudocode for A* (e.g., in your textbook or on Wikipedia) and see for yourself what it really does on that graph. – David Richerby May 9 '18 at 14:29
• @DavidRicherby Because A* is greedy, and C's F value is lower than B's the algorithm will choose C first. So there will be a step 'in its runtime', when A* thinks the shortest path will go through C. Thats not true, and A* will also fix the path. My question is about, that I thought consistent heuristic means that the algorithm wont consider any misleading path's in its 'run'. – toto8080 May 9 '18 at 14:55

A* isn't finished until all nodes with $f(n) < f(goal)$ are expanded.
So even though you have added $D$ to the open set you still need to expand $B$ because $f(B) = 11 < f(D) = 17$ after which $f(D)$ will become $12$