Uninformed search

Uniform-Cost Search (UCS)

Always expand the cheapest-so-far path first — guaranteed lowest total cost.

On the Sydney → London problem, Uniform-Cost Search finds: Sydney → Colombo → Dubai → London — total 22.0h.

The idea

Uniform-Cost Search (UCS) explores a graph by always growing the path that is cheapest so far, measured by g(n), the total cost from the start to node n. It never guesses about the future (that makes it "uninformed") — it only trusts the real costs it has already paid. Because it always finishes the cheapest option first, it is guaranteed to find the least-expensive route to the goal. It is Dijkstra's algorithm dressed up as a search.

How it works

Put the start node into OPEN (the frontier) with cost g = 0. CLOSED (already-expanded nodes) is empty.
Pick from OPEN the node with the smallest g(n) — the cheapest path found so far. This is the key rule of UCS.
If that node is the goal, stop and return its path — you have the cheapest route.
Otherwise move the node from OPEN into CLOSED, marking it as fully expanded.
Look at each neighbor and compute a new cost: g(node) + cost of the edge to that neighbor.
If the neighbor is not in OPEN or CLOSED, add it to OPEN with this new cost and remember node as its parent.
If the neighbor is already in OPEN but this new cost is cheaper, update it to the smaller cost (and new parent).
Repeat from step 2 until the goal is expanded or OPEN is empty (no path exists).

See it step by step

Watch Uniform-Cost Search search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Start at Sydney. OPEN (the frontier) holds just Sydney.

Expanding

OPEN — frontier

CLOSED — traversal

Path so far

Cost so far

Step 1 / 8

OPEN, CLOSED & the data structures

OPEN is a priority queue (a "min-heap") ordered by g(n): it always hands back the node whose total path cost from the start is smallest, which is what makes UCS optimal. CLOSED is a set of nodes already expanded; checking membership in it stops us from re-processing a node we've already settled on. Together they ensure every node is finalized exactly once, at its cheapest cost.

Pseudocode

function UCS(start, goal):
    OPEN  = priority queue ordered by g   # frontier
    CLOSED = empty set                     # expanded nodes
    add start to OPEN with g(start) = 0

    while OPEN is not empty:
        node = OPEN.pop_min_g()            # cheapest path so far
        if node == goal:
            return path(node)              # cost-optimal
        add node to CLOSED
        for each (neighbor, edge_cost) of node:
            new_g = g(node) + edge_cost
            if neighbor not in OPEN and neighbor not in CLOSED:
                add neighbor to OPEN with g = new_g, parent = node
            else if neighbor in OPEN and new_g < g(neighbor):
                update g(neighbor) = new_g, parent = node
    return failure                         # OPEN empty, no path

At a glance

Complete?Yes — it finds a solution if one exists (as long as costs don't drop toward negative infinity), because it systematically expands ever-costlier paths.

Optimal?Yes — cost-optimal with non-negative edge costs, since the goal is only accepted once it is the cheapest node in OPEN.

TimeO(b^(1 + C*/ε)) roughly — where C* is the optimal cost and ε the smallest edge cost; equivalently O(E + V log V) with a heap, since work grows with total cost, not just depth.

SpaceO(b^(1 + C*/ε)) — can be large because every generated node may sit in OPEN or CLOSED at once; memory is its main weakness.

👍 When to use it

Edges have different costs (distances, times, prices) and you need the truly cheapest path.
You have no reliable heuristic estimate to guide the search (so A* isn't available).
All edge costs are non-negative — the condition UCS relies on for optimality.
Finding shortest paths in a weighted map, network, or graph, where it is literally Dijkstra's algorithm.

⚠️ Watch out for

Do not confuse it with Breadth-First Search: BFS counts steps (fewest edges); UCS sums costs (cheapest total). They only match when every edge costs the same.
Negative edge costs break the optimality guarantee — UCS may settle a node too early. Use Bellman-Ford instead.
Check for the goal when you EXPAND (pop) a node, not when you first generate it — stopping early on generation can return a non-cheapest path.
Memory can blow up: OPEN plus CLOSED may hold a huge fraction of the graph, since UCS keeps no future estimate to prune with.

Now see it for yourself

Open Uniform-Cost Search in the visualizer — step through it, pause, and watch OPEN & CLOSED change.

▶ Watch it run