Uniform cost search can be achieved by implementing the fringe as a priority queue ordered by path cost. The algorithm shown below is almost same as BFS; except for the use of a priority queue and the addition of an extra check in case a shorter path to any node is discovered.

The algorithm takes care of nodes which are inserted in the fringe for exploration, by using a data structure having priority queue and hash table

The priority queue used here contains total cost from root to the node. Uniform cost search gives the minimum path cost the maximum priority.

The algorithm using this priority queue is the following:

Algorithm:

1. Insert the root node into the queue.

2. While the queue is not empty:

i. Dequeue the maximum priority node from the queue.

(If priorities are same, alphabetically smaller node is chosen)

ii. If the node is the goal node, print the path and exit.

Else

Insert all the children of the dequeud node, with their total costs as priority.

Performance Evaluation:

Completeness: Completeness is guaranteed provided the cost of every step exceeds some small positive constant.

Optimality: It produces optimal solution as nodes are expanded in order of their path cost.

Time complexity:

Uniform cost search considers path costs rather than depths; so its complexity is does not merely depends on b and d. Hence we consider C* be the cost of the optimal solution, . Then the algorithm’s worst-case time and space complexity is O(bC*/C), which can be much better than bd.

Space complexity:

O(bC*/C), indicating number of node in memory at execution time.