A* algorithm example - is it correct

I've following graph:

enter image description here

If I use A* algorithm, I get this sollution:

                      S (0+1=1)
                    /          \
                  /             \
          a(3+3=6)                b(2+3=5)
        /    |    \                /       \
      /      |     \              /         \
  c(4+0=4) b(6+3=9) d(6+0=6)    d(5+0=5)    c(7+0=7)

Question: which solution will we find, using algorithm A* and heuristic estimates(see graph)

Sollution:

select b(=5):

                  S (0+1=1)
                /          \
              /             \
      a(3+3=6)               b(2+3=5)

select d(=5):

                 S (0+1=1)
                /          \
              /             \
      a(3+3=6)                b(2+3=5)
                               /       \
                              /         \
                            d(5+0=5)    c(7+0=7)

Stop searching - because "cost 5" is less than a(3+3=6) -> we don't search for other solutions ? Solution is: s-b-d, cost = 5

Is it right ?

Solution

Theoretically looking at what you have written it is correct. However, there is one very important property of graphs you run A* on that should be valid so that you know the algorithm produces optimal solution: The heuristic function you use should be optimistic, i.e. never overestimate the real distance to the goal. If I get it correctly you have couple of goal nodes C and D and the problem is that the heuristic value of A is not optimistic, actually it overestimates (the path from A to the goal node C is only 1, which is less than h(A) = 3). This is why you actually do not get optimal solution.