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 word relationship:
“Women, because of their colonial relationship to men, have to fight for their own independence. This fight for our own independence will lead to the growth and development of the revolutionary movement in this country. Only the independent woman can be truly effective in the larger revolutionary struggle.”
—Women’s Liberation Workshop, Students for a Democratic Society, Radical political/social activist organization. “Liberation of Women,” in New Left Notes (July 10, 1967)