**Uniform cost search** is a tree search algorithm related to breadth-first search. Whereas breadth-first search determines a path to the goal state that has the least number of edges, uniform cost search determines a path to the goal state that has the lowest weight.

## Algorithm

Let $ T = (V,E) $ be a tree with weighted edges and let $ w(p) $ be the weight of path $ p $ in $ T $. For convenience, let $ r $ be the root of the tree and $ t(p) $ denote the end vertex of a path $ p $ in $ T $.^{[1]} With that said, let $ K $, the set of known paths starting with $ r $, be $ \{(r)\} $. It should be noted that the weight of $ (r) $ is zero.

- If there exists $ p $ in $ K $ such that $ p $ minimizes $ w(p) $ and $ t(p) $ is a goal state of $ T $, i.e., a leaf, stop. $ p $ is the path of minimal cost to the goal.
- Otherwise, identify $ p $ in $ K $ where $ p $ minimizes $ w(p) $ and
*expand*$ t(p) $. In other words, add to $ K $ all paths formed by adding one of the child vertices of $ t(p) $ (if any) to $ p $. Remove $ p $ from $ K $; it is considered 'visited', and failure to remove it may result in non-termination of the search. - Repeat first step.

## Additional Details

It's worth observing that uniform cost search assumes that no edges have negative weight. If any edges have negative weight, then it is possible that a path $ p $ begins with a vertex whose edge to its parent has a high positive weight, which will exclude it from consideration by the search. This action might be faulty, though, because the *total* weight of $ p $ might be minimal overall, due to negative weights further on in the path. When there are negative weights in the search tree, more expensive algorithms such as the Floyd-Warshall algorithm must be used.

## Notes

- ↑ This mapping might have been named $ e(p) $, but the author could not pass up the opportunity to use something that sounds like 'T.P.'.