AlgoInsight

Q&A

What is a uniform cost search algorithm?

By AlgoInsight Team2026-06-07algorithmsdata-structures

Overview

When edges all cost the same, Breadth-First Search finds the shortest path. But when edges have different costs, BFS's "fewest edges" is no longer "cheapest." Uniform Cost Search generalizes BFS to weighted graphs: instead of expanding by depth, it always expands the frontier node with the smallest accumulated cost g(n) from the start. This guarantees the first time it reaches the goal, it does so optimally.

graph TD
    A[Start] --> B[Frontier: priority queue ordered by g(n)]
    B --> C[Pop lowest-cost node]
    C --> D{Goal?}
    D -->|yes| E[Return optimal path]
    D -->|no| F[Expand neighbors,<br/>push with updated g&#40;n&#41;]
    F --> B
    style B fill:#1e1b4b,color:#fff

How It Works

  1. Put the start node in a priority queue with cost 0.
  2. Pop the node with the lowest cumulative cost g(n).
  3. If it's the goal, return the path (it's optimal).
  4. Otherwise, for each neighbor, compute the new cost g(n) + edge_cost, and push it onto the queue (updating if a cheaper path to it is found).
  5. Repeat until the goal is popped or the queue is empty.

The key idea: expand by lowest path cost, not by depth. Checking the goal when popped (not when first discovered) is what preserves optimality.

Pseudocode / Python

import heapq

def uniform_cost_search(graph, start, goal):
    # graph: dict node -> list of (neighbor, cost)
    frontier = [(0, start, [start])]   # (cumulative_cost, node, path)
    best_cost = {start: 0}

    while frontier:
        cost, node, path = heapq.heappop(frontier)
        if node == goal:
            return cost, path           # optimal: goal popped with least cost

        for neighbor, edge_cost in graph[node]:
            new_cost = cost + edge_cost
            if neighbor not in best_cost or new_cost < best_cost[neighbor]:
                best_cost[neighbor] = new_cost
                heapq.heappush(frontier, (new_cost, neighbor, path + [neighbor]))

    return float("inf"), []             # goal unreachable

# Example
graph = {
    "A": [("B", 1), ("C", 5)],
    "B": [("C", 2), ("D", 4)],
    "C": [("D", 1)],
    "D": []
}
print(uniform_cost_search(graph, "A", "D"))   # (4, ['A', 'B', 'C', 'D'])

Note the optimal path A→B→C→D costs 4, beating the direct-looking A→C→D (5+1=6) - UCS finds the cheapest, not the fewest-hops.

Why Goal-Test on Pop (not on Generation)?

If you returned the moment you generated the goal, you might return a more expensive path discovered early. By testing only when a node is popped (i.e., it has the lowest cost in the frontier), you guarantee no cheaper path to it remains - that's the optimality guarantee.

Properties

Property UCS
Complete Yes (if costs > 0 and a solution exists)
Optimal Yes (with non-negative edge costs)
Time O(b^(1 + ⌊C*/ε⌋)) ≈ exponential in worst case; in graph terms O(E + V log V) with a good PQ
Space Can be large - stores the whole frontier
where b = branching factor, C* = optimal cost, ε = minimum edge cost.

UCS vs Related Searches

Limitations

Why This Matters in Interviews

AI/algorithms interviews use UCS to test understanding of cost-based search, the priority-queue mechanism, and the relationship to BFS, Dijkstra, and A*. The two highest-value points: (1) UCS = Dijkstra = A* with h=0, and (2) you must goal-test on pop, not on generation, to keep optimality. Stating the non-negative-cost requirement shows rigor.

Common Pitfalls

References

More answers