1. Uniform-Cost Search

Uniform-cost search (UCS) is an uninformed search algorithm that expands nodes in order of increasing path cost \(g(n)\) ¹. It is the state-space generalisation of Dijkstra's shortest-path algorithm: where Dijkstra operates on an explicit graph in memory, UCS explores an implicitly defined state space, generating successors on demand. UCS is both complete (it will find a solution if one exists, given finite branching and positive edge costs) and optimal (the first solution found has the minimum path cost).

1.1 Problem Statement

Given a state-space search problem with:

• A start state \(s_{\text{start}}\)
• A goal test \(\text{GOAL}(s)\)
• A successor function \(\text{SUCC}(s)\) returning (state, action, cost) triples
• All step costs \(c > 0\)

find a path from \(s_{\text{start}}\) to any goal state that minimises the total path cost \(g\).

1.2 Algorithm

UCS maintains a priority queue (min-heap) keyed on \(g(n)\), and a visited set to avoid re-expanding states with a known-optimal cost.

UCS(start, goal_test, succ):
  frontier = MinHeap()                   // keyed on g-cost
  frontier.insert((0, start, []))        // (g, state, path)
  visited  = {}                          // state → best g seen

  while frontier is not empty:
    (g, s, path) = frontier.pop_min()
    if s in visited:                     // already settled at lower cost
      continue
    visited[s] = g
    if goal_test(s):
      return path + [s], g              // optimal path found
    for (s', action, cost) in succ(s):
      if s' not in visited:
        frontier.insert((g + cost, s', path + [s]))
  return FAILURE

1.3 Relation to Dijkstra's Algorithm

UCS and Dijkstra's algorithm are conceptually identical. The technical distinctions are engineering concerns:

Both maintain the greedy settlement invariant: when a node is first popped from the priority queue, its \(g\)-value is optimal. The proof is the same in both cases — any alternative path would go through an unsettled node with at least as high a priority, contradicting it being shorter.

1.4 Completeness and Optimality

Completeness: If a solution exists and every step cost is \(\geq \varepsilon > 0\), then at depth \(d\) of the optimal solution the path cost is at most \(C^*\). UCS must expand all nodes with cost \(< C^*\) before reaching the goal; since each expansion increases cost by at least \(\varepsilon\), the number of expansions before the goal is finite. \(\square\)

Optimality: Suppose UCS returns a path of cost \(c' > C^*\). Then an optimal path of cost \(C^*\) exists. Its nodes were never all expanded — but since \(C^* < c'\), they would have lower priority and be expanded earlier. Contradiction. \(\square\)

1.5 Complexity

Let \(C^*\) be the optimal cost and \(\varepsilon\) the minimum step cost. In the worst case UCS explores all states whose cost \(\leq C^*\):

When all step costs are equal (\(\varepsilon = 1\), equal costs), \(C^* = d \cdot 1\), so the bounds reduce to \(O(b^{d+1})\) — equal to BFS.

UCS can be dramatically more efficient than BFS when step costs vary and the optimal solution is at shallow depth with low cost.

1.6 Comparison with Related Algorithms

UCS is equivalent to A* with \(h \equiv 0\). Adding an admissible heuristic \(h\) yields A*, which can skip large portions of the search space by using domain knowledge.

1.7 Interactive Demo

The canvas below runs UCS on a 9×9 grid with positive integer edge weights. The orange dashed frontier shows the current priority queue; settled cells display their \(g\)-cost. The path from (0,0) to (8,8) is highlighted in green on completion.