The problem is Best-First Search (Best First Search) isn't optimal (finds the path of lowest cost), whereas A* and Dijkstra/UCS (Uniform Cost Search) are. (It s

The problem is Best-First Search (Best First Search) isn't optimal (finds the path of lowest cost), whereas A* and Dijkstra/UCS (Uniform Cost Search) are. (It should be noted Best-First Search is a family of search algorithms, of which A* and Dijkstra are a part of). Here, Best-First Search uses geometric distance (estimated with a heuristic) from the goal to prioritise nodes. UCS uses pathcost only and A* uses the sum of pathcost and heuristic. This means this implementation of Best-First Search will expand nodes that are closest to the goal first, even if it has a high path cost. A simple example is a straight path and a path with lots of twists, with the straight path starting a few nodes further away from the goal. Best-First Search will proceed on the path with twists first, till it reaches the goal. The result of this Best-First Search isn't optimal, since the straight path is shorter. Both A* and UCS will get the shorter path (there are conditions though, UCS needs strictly positive path weights, and the distance heuristic must be an underestimate).