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:
“Artists have a double relationship towards nature: they are her master and her slave at the same time. They are her slave in so far as they must work with means of this world so as to be understood; her master in so far as they subject these means to their higher goals and make them subservient to them.”
—Johann Wolfgang Von Goethe (1749–1832)
“It was a real treat when he’d read me Daisy Miller out loud. But we’d reached the point in our relationship when, in a straight choice between him and Henry James, I’d have taken Henry James any day even if Henry James were dead and not much of a one for the girls when living, either.”
—Angela Carter (1940–1992)