The idea: search blind, but in a smart order

A search problem has a start state, a goal test, and actions that lead from one state to the next, each with a cost. An uninformed (blind) search knows nothing about where the goal is. It can only choose the order in which it tries paths. Two orders matter most before A*: cheapest path first, and shallowest path first with little memory.

The page's graph from S to G. The path S→B→G has only 2 edges but costs 4 + 9 = 13. The path S→C→E→G has 3 edges and costs 2 + 1 + 3 = 6. Uniform-cost search returns the cheap one, iterative deepening the short one
Fewest edges is not cheapest: IDDFS returns S→B→G (2 edges, cost 13), UCS returns S→C→E→G (3 edges, cost 6).

The canvas uses one directed graph with 8 nodes. S is the start and G the goal; the purple numbers are edge costs. Children are tried in alphabetical order. Pick a search and press Search, or run a demo. The table at the bottom keeps each search's result so you can compare them.

Uniform-cost search: cheapest first

Uniform-cost search (UCS) keeps a frontier of paths waiting to be extended, in a priority queue ordered by the path cost g(n). Each step it pops the entry with the lowest g and expands it: every child gets g + edge cost. A new child joins the frontier; a child already there is replaced only if the new path is cheaper. A node that was already expanded is skipped, because it was reached more cheaply before (Demo 1: uniform-cost search, cheapest first).

frontier = priority queue with (S, g = 0)
while frontier not empty:
    n = pop lowest g
    if n is the goal: return path to n
    mark n explored
    for each child c of n with edge cost w:
        if c not explored and (c not on frontier or g(n) + w < g(c)):
            put c on the frontier with g(c) = g(n) + w

This is Dijkstra's algorithm with an early stop at the goal. On the page's graph it pops S, A, C, D, E, B and then G, with cost 6. Two moments are worth watching. E first gets g = 6 through A, then C finds a path costing 3 and replaces it. G first gets g = 9 through D, then E finds 6.

Test for the goal when you pop, not when you push

When D is expanded, G is generated with g = 9. If the search stopped there, it would return S→A→D→G with cost 9 (Demo 2: goal test too early gives cost 9). The cheaper path through E was still on the frontier, behind entries with smaller g. Only when G comes off the queue is every other waiting path at least as expensive, so only then is its cost final. Breadth-first search may test at generation because there all edges cost the same.

Iterative deepening: deepen the limit, keep little

Depth-limited search is depth-first search that does not go below depth L. Iterative deepening DFS (IDDFS) runs it with L = 0, 1, 2, … until it finds the goal. Each round starts from scratch. The stack panel on the canvas holds only the current path, and a node is popped as soon as its children are done (Demo 3: iterative deepening, limits 0, 1, 2).

Three rounds of iterative deepening drawn as trees. Limit 0 visits S only. Limit 1 visits S, A, B, C. Limit 2 visits S, A, D, E, B and then G, where it stops. Visits: 1 + 4 + 6 = 11
Each round repeats the rounds before it and goes one level deeper: 1 + 4 + 6 = 11 visits to find G at depth 2.

The repeated work is smaller than it looks. With branching factor b, the deepest level holds most of the nodes, so the upper levels searched again add only a constant factor: about b/(b − 1) times the work of a single search to that depth. In return, memory stays at the length of the path (times b if the siblings are stored).

IDDFS returns the goal with the fewest edges, like breadth-first search. It ignores costs, so on this graph it finds S→B→G with cost 13. Set edge costs to all 1 and both searches return S→B→G with cost 2: when every step costs the same, uniform-cost search expands nodes in the same order as BFS (Demo 5: all costs 1).

Side by side

Demo 4: UCS vs IDDFS fills the table with both runs: UCS visits 7 nodes but keeps up to 8 in memory (the whole graph), while IDDFS visits 11 and never keeps more than 3.

uniform-cost searchiterative deepening DFS
orderlowest path cost g firstdepth first, limit 0, 1, 2, …
complete?yes, if every cost ≥ some ε > 0yes, on a finite branching factor
optimal?yes, cheapest pathfewest edges only (cheapest when all costs are equal)
timeO(b1 + ⌊C*/ε⌋)O(bd)
memoryO(b1 + ⌊C*/ε⌋): frontier and explored setO(b·d): the current path
on this graphS→C→E→G, cost 6, 7 visits, peak 8 nodesS→B→G, cost 13, 11 visits, peak 3 nodes

Here C* is the cost of the best path, ε the smallest edge cost and d the depth of the shallowest goal. A* keeps the UCS frontier but orders it by g + h, adding a guess h of the remaining cost; IDA* does the same trick for iterative deepening, with a cost limit instead of a depth limit.

See also BFS vs DFS for the two plain orders, Dijkstra's algorithm for the same cost order over a whole graph, A* Search for what a heuristic adds, and Minimax, where game engines use iterative deepening.

What the page leaves out

Graphs with cycles (IDDFS then checks the current path, UCS the explored set); bidirectional search; depth-limited search on its own; iterative lengthening (a cost limit instead of a depth limit); IDA* and other informed searches; tie-breaking rules beyond first in, first out.