Uniform-Cost Search (Dijkstra)

Uniform-cost search (UCS), also known as Dijkstra's algorithm, expands the node with the lowest cumulative path cost $g(n)$ first. Frontier is a priority queue ordered by $g$.

Algorithm

``` function UCS(initial, goal): frontier = PriorityQueue([(0, initial, [])]) visited = {} while frontier not empty: (cost, state, path) = frontier.pop_min() if state is goal: return path if state in visited and visited[state] <= cost: continue visited[state] = cost for action in actions(state): next = transition(state, action) next_cost = cost + step_cost(state, action) frontier.push((next_cost, next, path + [action])) return failure ```

Properties

• Complete: yes, with non-negative step costs and finite branching factor.
• Optimal: yes — always finds the cheapest path because we pop lowest-cost first.
• Time and space: $O(b^{1+\lfloor C^*/\epsilon \rfloor})$ where $C^*$ is optimal cost and $\epsilon$ is the smallest step cost. Effectively $O(b^d)$ when costs are uniform.

Why pop-then-skip rather than relax-once

A state can be enqueued multiple times with different costs (different paths reach it). The "if visited and visited[state] <= cost: continue" check ensures we only process the cheapest version. With a Fibonacci heap and decrease-key you can do better in theory; in practice the lazy version with a priority queue is simpler and roughly as fast.

When UCS is the right tool

• Step costs aren't uniform.
• You need the optimal path, not just any path.
• You have no heuristic. (If you do have one, use A* — strictly stronger.)

UCS is essentially BFS-with-priority. Its main weakness is the same: $O(b^d)$ time without any pruning. Use it as the baseline; reach for A* when you have problem-specific knowledge to inject as a heuristic.

Negative weights

UCS / Dijkstra requires non-negative step costs. With negative weights, the "popped first means cheapest" invariant breaks: you can find a state, mark it processed, and later discover a cheaper path through a negative edge. Use Bellman-Ford for graphs with negative weights but no negative cycles; no efficient algorithm exists for graphs with negative cycles.