A search algorithm used for traversing a weighted tree or graph. The algorithm comes into play when a different cost is available for each edge. The primary goal is to find a path to the goal node which has the lowest cumulative cost. Uniform-cost search expands nodes according to their path costs form the root node. It can be used to solve any graph/tree where the optimal cost is in demand and is equivalent to the BFS algorithm if the path cost of all edges is the same.

An example: Order in which the nodes are expanded

Properties:

  • Completeness: yes, for finite b and step cost >= e for positive e
  • Optimality (Admissibility): yes
  • Time Complexity: O(b(1+C/e)
  • Space Complexity: O(b(1+C/e)), b – branching factor, C – optimal cost, C/e – a number of steps to goal, e – min cost of each action