#admissible-heuristic

A directed graph has the edges S→A (cost 1), S→B (3), A→B (1) and B→G (3). The heuristic is $h(S) = 0$, $h(A) = 4$, $h(B) = 0$, $h(G) = 0$: it never overestimates the true cost to G, but $h(A) > c(A, B) + h(B)$. A* runs as a graph search that never re-expands a node it has already expanded, with the goal test applied when a node is taken off the frontier. What is the cost of the path it returns?