Uniform-Cost Search

Uniform-Cost Search is a graph search algorithm that extends Breadth-First Search to weighted graphs. Where BFS assumes all edges have equal cost and finds the path with the fewest edges, uniform-cost search finds the path with the lowest total cost, summing edge weights along the path. It is the limiting case of A* search where the heuristic function is identically zero.

The algorithm maintains a priority queue ordered by path cost from the source. It expands the node with the lowest cumulative cost, ensuring that when a node is first extracted from the queue, the shortest path to it has been found. This is Dijkstra's algorithm without the requirement that all edge weights be non-negative. When edge weights are non-negative, uniform-cost search and Dijkstra's algorithm are equivalent.

Uniform-cost search occupies the boundary between informed and uninformed search. It uses more information than BFS (edge weights) but less than A* (no heuristic). It is the correct algorithm for systems that know the cost of each edge but have no model of which direction is promising. The algorithm is complete and optimal for graphs with non-negative edge weights, but it explores nodes in order of increasing cost, which may be expensive if the goal is deep and the branching factor is high.

The systems-theoretic insight is that uniform-cost search represents a system with partial information: it knows the local cost of each action but not the global structure of the environment. This is the typical case for real systems, which know the cost of their immediate options but not the full cost of reaching a distant goal.