## Definition **Uniform Cost Search (UCS)** is the generalisation of [[Breadth-First Search|BFS]] to **weighted edges**. It expands the node with the **lowest path cost $g(n)$ from the start** first, using a priority queue. ## Algorithm ``` frontier ← priority queue with (cost=0, initial_state) explored ← ∅ while frontier is non-empty: (g, node) ← pop_min(frontier) if isGoal(node.state): return path(node) explored.add(node.state) for each action a in A(node.state): child ← expand(node, a) new_cost ← g + cost(node, a, child) if child.state not in explored: insert_or_update(frontier, new_cost, child) return failure ``` ## Properties - **Complete:** yes, provided action costs are strictly positive ($\geq \epsilon > 0$). - **Optimal:** yes — the first time a goal node is popped from the priority queue, its path is optimal. - **Time and space:** $O(b^{1 + \lfloor C^*/\epsilon \rfloor})$ where $C^*$ is the optimal cost. ## Why Strictly Positive Costs Zero-cost edges can introduce infinite loops between same-cost states. With $\epsilon$ as a positive lower bound on costs, the algorithm terminates. ## Relationship to Dijkstra UCS *is* Dijkstra's shortest-path algorithm, framed as state-space search. The implementation is identical; the difference is that classical Dijkstra operates on an explicit graph, while UCS lazily expands states from a problem definition. ## Connection to A* [[A Star Algorithm]] is UCS plus a heuristic $h$: - UCS orders by $g(n)$ (cost so far). - A* orders by $f(n) = g(n) + h(n)$ (cost so far + estimated remaining). When $h(n) = 0$, A* reduces to UCS. ## Related - [[Uninformed Search]] - [[Breadth-First Search]] - [[A Star Algorithm]]