Does the A* algorithm visit every node?
It only flood-fills the graph if there is no path to the end-node.

What would be the point of including a heuristic if you were just going to visit every node anyways?