A* is optimal in the sense that it is guaranteed to find the optimal solution (shortest path), there are no guarantees in terms of speed IIRC.