Uniform Cost Search Algorithm

Uniform cost search is a graph search algorithm, used especially in artificial intelligence, that finds the lowest cost path from a starting point to a goal by always expanding whichever frontier node currently has the lowest total path cost from the start, tracked through a priority queue. Rather than working over a graph whose full structure and distances are already known in advance, as classic shortest path problems typically assume, uniform cost search discovers the graph as it goes, adding newly found nodes to its priority queue only as it encounters them, which suits searching very large or effectively infinite spaces such as those found in planning and puzzle solving. The algorithm is essentially Dijkstra's algorithm applied in this incremental, search oriented way rather than to a graph that is entirely known beforehand, and when every edge in the graph has the same cost it reduces exactly to breadth first search, since the priority queue then behaves like an ordinary first in, first out queue.