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