Can it handle zero-cost edges?

Correct finite graph implementations can handle them, but uncontrolled tree search can revisit zero-cost cycles indefinitely. Infinite-space guarantees need additional care.

Is it the same as greedy best-first search?

No. Greedy best-first uses estimated remaining cost; uniform-cost uses cost already accumulated.

What if several paths tie?

A tie-breaking rule chooses among equal priorities. Several distinct optimal solutions may exist.

AI Glossary / Graphs and symbolic AI / Intermediate

Uniform-cost search

Definition

Uniform-cost search explores paths in order of their accumulated cost from the starting point. At each step it selects a frontier node with the smallest path cost, usually written g(n). With appropriate nonnegative-cost assumptions and correct bookkeeping, it finds a least-cost solution.

What it means

The cheapest next action is not necessarily part of the cheapest complete route. Uniform-cost search compares the totals of competing partial paths rather than greedily selecting the smallest individual edge.

It also differs from breadth-first search. Breadth-first search prioritizes the number of steps; uniform-cost search prioritizes their sum of costs. When every step has the same positive cost, these priorities coincide apart from tie handling.

Uniform-cost search does not use an estimate of the cost still required to reach the goal. It is therefore an uninformed search method, despite using known action costs. In graph settings, its principle is closely associated with Dijkstra's shortest-path algorithm.

How it works

Place the start on a priority queue with cost zero. Remove the cheapest available entry, and test whether it reaches a goal. Otherwise, generate successors and add each action's cost to the path total.

A graph-search implementation tracks the best known cost of reaching each state. If a cheaper route to a state is found, update its candidate path or add an improved queue entry and later ignore obsolete entries. Marking a state permanently finished when it is merely first discovered is generally incorrect.

Nonnegative edge costs support the usual least-cost argument on finite graphs. For standard completeness guarantees in infinite, finitely branching search spaces, a positive lower bound on step cost prevents infinitely many arbitrarily cheap steps from blocking progress. Negative costs require different reasoning and algorithms; a negative cycle can make a finite optimum nonexistent.

Three practical examples

A route planner finds the least total toll among represented routes with nonnegative toll costs.
A workflow model finds a minimum-cost sequence of allowed operations when each operation has a defined nonnegative cost.
A game-development tool searches for a movement path that minimizes accumulated terrain cost rather than the number of grid steps.

Think of it this way

Think of a growing wave spreading outward according to travel expense rather than physical distance. A long chain of cheap connections may be reached before a short but costly connection.

The wave is a mathematical search over the supplied model. It does not measure real expenses automatically, and it cannot make an omitted restriction or inaccurate edge cost disappear.

Worked example

Why the first discovered goal is not enough

Use an invented directed graph with edges S→G costing 12, S→A costing 2, S→B costing 5, A→B costing 1, A→G costing 9 and B→G costing 3.

After expanding S, the frontier contains A at cost 2, B at cost 5 and goal G at cost 12. Returning G immediately would be premature. Expanding A first improves B to cost 3 and G to cost 11, because 2 + 9 = 11.

Next, expand B at cost 3. Its edge to G improves the goal cost to 3 + 3 = 6. When G at cost 6 is selected as the cheapest current frontier entry, the algorithm returns S→A→B→G. The path has three edges, but costs half as much as the one-edge route. Any obsolete B-at-5 entry must be ignored rather than treated as a better route.

Illustrative case study

The fictional MapleRoutes team builds a facility-routing tool. Its first version stops as soon as it generates an exit node. This produces a valid path, but sometimes misses a cheaper route discovered through another corridor.

The team changes the stopping rule to accept the goal when it is removed as the cheapest valid frontier entry. It also updates previously discovered rooms when a cheaper path reaches them. A separate review checks whether restricted corridors were incorrectly included in the graph.

The case illustrates algorithm correctness and model correctness as distinct concerns. It reports no real travel savings or production benchmark.

Common misconceptions and mistakes

Uniform-cost search always chooses the cheapest next edge. It selects the smallest accumulated path cost among frontier entries.
The first goal generated is guaranteed optimal. The standard guarantee relies on the appropriate goal-selection stopping rule.
Uniform means all edges must have equal cost. Different nonnegative costs are precisely why this method is useful.

Business use

Uniform-cost search provides a transparent baseline for least-cost planning when no useful remaining-cost heuristic is available. Its returned path can be explained by the sequence of actions and the sum of their costs.

Its main limitation is the number of inexpensive partial paths it may explore before reaching a goal. Time and memory can become substantial. Check that the state representation retains everything needed to determine future options and costs. If cost depends on history, the state may need to include that history's relevant features. Consider A* when a suitable heuristic can guide exploration while preserving the required guarantee.

Check your understanding

A direct goal path costs 20, while another frontier path costs 4 and has not yet been explored. Is discovering the goal sufficient to stop optimally?

Answer: No. The cheaper partial path may lead to a goal costing less than 20. Continue until the correct least-cost stopping condition is met.

Related terms

Dijkstra's algorithm
Breadth First Search
Priority queue
Graph search
Shortest Paths
path cost
A* search
nonnegative edge
shortest path

Learn next

Read priority queues and Dijkstra's algorithm. Trace the worked graph with a table of best-known state costs, showing why an earlier, more expensive queue entry becomes obsolete.

Dijkstra's algorithm

Sources

Stuart Russell and Peter Norvig, author-hosted search chapter, uniform-cost search discussion: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf

NetworkX developers, single_source_dijkstra documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html

The relevant primary explanations were reviewed. The distinction between finite graph handling and infinite tree-search assumptions is retained. The six-edge worked example is original and its competing path totals were checked.

Previous: Uniform convergence theory Next: Uniform distribution