Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

general
communitycreator

What is uniform-cost search?

Fatima Hasan

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Uniform-cost search is an uninformed search algorithm that uses the lowest cumulative cost to find a path from the source to the destination. Nodes are expanded, starting from the root, according to the minimum cumulative cost. The uniform-cost search is then implemented using a Priority Queuethe lesser the cumulative cost, the higher the priority.

Algorithm for uniform cost search:

  • Insert the root node into the priority queue

  • Repeat while the queue is not empty:
    Remove the element with the highest priority
    If the removed node is the destination, print total cost and stop the algorithm
    Else, enqueue all the children of the current node to the priority queue, with their cumulative cost from the root as priority

Example graph

First, we just have the source node in the queue:

Then, we add its children to the priority queue with their cumulative distance as priority:

Now, A has the minimum distance (i.e., maximum priority), so it is extracted from the list. Since A is not the destination, its children are added to the PQ.

B has the maximum priority now, so its children are added to the queue:

Up next, G will be removed and its children will be added to the queue:

C and I have the same distance, so we will remove alphabetically:

Next, we remove I; however, I has no further children, so there is no update to the queue. After that, we remove D.
D only has one child, E, with a cumulative distance of 10. However, E already exists in our queue with a lesser distance, so we will not add it again. \

The next minimum distance is that of E, so that is what we will remove:

Now, the minimum cost is F, so it will be removed and its child (J) will be added:

After this, H has the minimum cost so it will be removed, but it has no children to be added:

Finally, we remove the Dest node, check that it is our target, and stop the algorithm here.

The minimum distance between the source and destination nodes (i.e., 8) has been found.

Time complexity

The time complexity needed to run uniform cost search is:

O(b(1 + C / ε))

Where:
b - branching factor
C - optimal cost
ε - cost of each step

RELATED TAGS

general
communitycreator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring