# Why does A* fail to find the fastest path when it reaches the goal?

I'm trying to understand how A* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A* "failed". Here is an example:

Take a 2x2 grid, in which you can only move in one of 4 (orthogonal) directions (no diagonal movement). Denote the node at (0, 0) by A, the node at (1, 0) by B, the node at (0, 1) by C, and the node at (1, 1) by D (so that it looks like C D A B The weight going from A to B is 3, the weight going from A to C is 2, the weight from B to D is 1, and the weight from C to D is 3. Let the start node be A and the goal be D. Let our heuristic simply be Euclidean distance (or Manhattan distance, both produce the same result in this instance).

So, if my understanding of A* is correct, we start with an open set containing only A, so we pop A. It's neighbours are B and C, which have g values g(B) = 3, g(C) = 2, and h values h(B) = 1, h(C) = 1. So the f-values are f(B) = 3 + 1 = 4, f(C) = 2 + 1 = 3. Add these to the open set.

Now the open set is {B, C}. Since C has the lowest f-value, we pop it. C's only neighbour is D, which is the goal. So we stop, having found "the best path" from A to D.

This is clearly wrong. The algorithm should output the path A->B->D, which has total weight 4, but instead it stopped prematurely.

Now, if we were to have a larger graph, then after exploring the path A->C->D we would go back to B (which is still in the open set), notice that the path A->B->D to D gives D a lower f-value than A->C->D, so we update D's f-value, giving the correct fastest path. Alternatively, we could simply continue running A* until the open set is empty, rather than ending prematurely as soon as we've found the goal (however, this doesn't agree with Wikipedia's pseudocode implementation of A*).

Are my ideas correct, or am I missing something about how A* is typically implemented?

So, in your example, when it pops $C$, it puts $D$ in the open list, with quite a high value. It then pops $B$ and puts $D$ in the open list again, with a lower value. So the first time that $D$ is popped will be from the route $A\to B\to D$, as it should be.