Relationship To Other Algorithms
Dijkstra's algorithm, which is perhaps better-known, can be regarded as a variant of uniform-cost search, where there is no goal state and processing continues until all nodes have been removed from the priority queue, i.e. until shortest paths to all nodes (not just a goal node) have been determined. As in Dijkstra's algorithm, UCS guarantees that (if all edge weights are non-negative) the shortest path to a particular node has been found once the node is extracted from the priority queue.
Uniform-cost search is a special case of the A* search algorithm if its heuristic is a constant function. If A* is used with a monotonic heuristic, then it can be turned into a uniform cost search by subtracting from each edge cost the decrease in heuristic value along that edge. Breadth-first search (BFS) is a special case of uniform-cost search when all edge costs are positive and identical. Where BFS first visits the node with the shortest path length (number of nodes) from the root node, UCS first visits the node with the shortest path costs (sum of edge weights) from the root node.
Uniform-cost search is a variant of best-first search.
Read more about this topic: Uniform-cost Search
Famous quotes containing the words relationship to and/or relationship:
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—Adrienne Rich (b. 1929)
“It would be a fallacy to deduce that the slow writer necessarily comes up with superior work. There seems to be scant relationship between prolificness and quality.”
—Fannie Hurst (1889–1968)