Uniform cost search (UCS) always expands the frontier node with the lowest path cost \(g(n)\) from the start, so it finds the cheapest path even when step costs differ.
Algorithm
- Put the start node in a priority queue with \(g = 0\).
- Remove the node with the smallest \(g\). If it is the goal, stop (the goal test is done when a node is expanded, not when it is generated).
- Otherwise expand it: for each child, \(g(\text{child}) = g(\text{node}) + \) step cost. Add the child, or replace an existing frontier entry if the new cost is lower.
- Repeat.
Example. Edges: S→A (1), S→B (5), A→G (9), B→G (3).
S
1 / \ 5
A B
9 \ / 3
G- Frontier {S:0}. Expand S → {A:1, B:5}.
- Expand A (1) → add G with cost 1 + 9 = 10 → {B:5, G:10}.
- Expand B (5) → G via B costs 5 + 3 = 8 < 10, so replace → {G:8}.
- Expand G (8) → goal. Path S → B → G, cost 8.
BFS would return S → A → G (fewest edges, cost 10); UCS returns the cheaper path. If we had stopped when G was first generated, we would also have got the wrong cost 10, which is why the goal test is done on expansion.
Properties (\(C^*\) = optimal cost, \(\varepsilon\) = smallest step cost):
- Complete: yes, if every step cost \(\ge \varepsilon > 0\).
- Optimal: yes.
- Time and space: \(O\!\left(b^{1+\lfloor C^*/\varepsilon\rfloor}\right)\).
UCS is the same as Dijkstra's algorithm applied to a search problem, and equals BFS when all step costs are equal.