Uniform Cost Search

Sorting is done in increasing cost of the path to a node. It always expands the least cost node. It is identical to Breadth First search if each transition has the same cost.

It explores paths in the increasing order of cost.

Disadvantage: There can be multiple long paths with the cost ≤ C*. Uniform Cost search must explore them all.