Uniform Cost Search (UCS)

In the previous lesson, we explored the A* search algorithm, which intelligently combines path cost and heuristic estimates to efficiently reach a goal.

In this lesson, we study a closely related but simpler algorithm — Uniform Cost Search (UCS).

Uniform Cost Search is a fundamental algorithm that guarantees the least-cost path in weighted graphs, even when edge costs are different.

Why Uniform Cost Search Exists

Breadth-First Search works well only when all edge costs are equal.

However, in real-world problems, different actions often have different costs.

Uniform Cost Search solves this problem by always expanding the path with the lowest total cost so far.

Core Idea of Uniform Cost Search

Uniform Cost Search always selects the node with the smallest accumulated cost from the start node.

It does not use heuristics. Instead, it relies purely on actual path cost.

This makes UCS:

• Optimal
• Complete
• Reliable for weighted graphs

Uniform Cost Search vs BFS

Although UCS looks similar to BFS, there is a crucial difference.

BFS expands nodes by depth, while UCS expands nodes by cost.

This difference allows UCS to handle unequal edge weights correctly.

Real-World Example

Imagine planning a delivery route.

Some roads are free highways, while others are toll roads.

The shortest path in terms of distance may not be the cheapest path.

Uniform Cost Search always finds the cheapest route, not just the shortest one.

How Uniform Cost Search Works

Uniform Cost Search uses a priority queue ordered by path cost.

The algorithm repeatedly:

1. Removes the lowest-cost node from the queue
2. Expands it
3. Adds its neighbors with updated costs

The first time the goal node is reached, the path is guaranteed to be optimal.

Pseudocode for Uniform Cost Search

priority_queue = [(0, start)]

while priority_queue is not empty:
    cost, node = extract_min(priority_queue)

    if node is goal:
        return cost

    for each neighbor of node:
        new_cost = cost + edge_cost(node, neighbor)
        add (new_cost, neighbor) to priority_queue

Why Uniform Cost Search Is Optimal

Uniform Cost Search always expands the lowest-cost path available.

This ensures that once a goal is reached, no cheaper path exists.

This property holds as long as all edge costs are non-negative.

Where Uniform Cost Search Is Used

Uniform Cost Search is used in:

• Network routing
• Logistics and transportation
• AI planning problems
• Robotics navigation

Exercises

Quick Quiz

In the next lesson, we will conclude the Algorithms module by studying Hill Climbing and Simulated Annealing, two important optimization techniques inspired by real-world processes.