For many domains, arcs have non-unit costs, and the aim is to find an optimal solution, a solution such that no other solution has a lower total cost. For example, for a delivery robot, the cost of an arc may be resources (e.g., time, energy) required by the robot to carry out the action represented by the arc, and the aim is for the robot to solve a given goal using fewest resources. The cost for a tutoring system may be the time and effort required by a student. In each of these cases, the searcher should try to minimize the total cost of the path found to a goal.

The search algorithms considered thus far are not guaranteed to find the minimum cost paths; they have not used the arc cost information at all. Breadth-first search finds a solution with the fewest arcs first, but the distribution of arc costs may be such that a path with the fewest arcs is not one of minimal cost.

The simplest search method that is guaranteed to find a minimum cost path is lowest-cost-first search, which is similar to breadth-first search, but instead of expanding a path with the fewest number of arcs, it selects a path with the lowest cost. This is implemented by treating the frontier as a priority queue ordered by the cost function.

If the costs of the arcs are all greater than a positive constant (bounded arc costs) and the branching factor is finite, the lowest-cost-first search is guaranteed to find an optimal solution – a solution with lowest path cost – if a solution exists. Moreover, the first path to a goal that is expanded is a path with lowest cost. Such a solution is optimal, because the algorithm expands paths from the start node in order of path cost. If a better path to a goal existed than the first solution found, it would have been expanded from the frontier earlier.

The bounded arc cost is used to guarantee the lowest-cost search will find a solution, when one exists, in graphs with finite branching factor. Without such a bound there can be infinite paths with a finite cost. For example, there could be nodes $n_0,n_1,n_2,\mathrm{\dots }$ with an arc for each $i>0$ with cost $1/2^i$. Infinitely many paths of the form all have a cost of less than 1. If there is an arc from $n_0$ to a goal node with a cost equal to 1, it will never be selected. This is the basis of Zeno’s paradox that Aristotle wrote about more than 2300 years ago.

Like breadth-first search, lowest-cost-first search is typically exponential in both space and time. It generates all paths from the start that have a cost less than the cost of a solution.