A searching algorithm for traversing a weighted tree or graph is uniform-cost search. This approach is applied when each edge has a separate cost. The main goal of the uniform-cost search is to find the shortest path to the goal node with the lowest cumulative cost. Based on their path costs, uniform-cost search grows nodes from the root node. It can be used to solve any graph or tree where the best price is required. The priority queue employs a uniform-cost search algorithm. It prioritizes the least expensive total cost. Uniform cost search is comparable to the BFS algorithm if all edges have the same path cost.
Advantages:
- It is always optimal because it only chooses the low cost path.
Disadvantages:
- It is only concerned with the cost of the path and is unconcerned with the number of steps required in the search. As a result, this algorithm may become trapped in a never-ending loop.
Code:
let’s assume S=0,A=1, B=2, C=3, D=4, G(right)=5, E=6, F=7 , G(middle)=8, g(left)=9
Output:
Completeness:
This Algorithm is complete.
Time Complexity:
C* =Cost of the optimal solution
ε = each step to get closer to the goal node
C*/ε+1= the number of steps
+1 because we start from state 0 and end to C*/ε.
Uniform-cost search’s worst-case time complexity of is O(b1 + [C*/ε])/.
Space Complexity:
Uniform-cost search’s worst-case space complexity is O(b1 + [C*/ε]).
