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:
“Film music should have the same relationship to the film drama that somebody’s piano playing in my living room has to the book I am reading.”
—Igor Stravinsky (1882–1971)
“Some [adolescent] girls are depressed because they have lost their warm, open relationship with their parents. They have loved and been loved by people whom they now must betray to fit into peer culture. Furthermore, they are discouraged by peers from expressing sadness at the loss of family relationships—even to say they are sad is to admit weakness and dependency.”
—Mary Pipher (20th century)