I was wondering what's the difference between uniform-cost search and Dijkstra's algorithm. They seem to be the same algorithm.
相关问题
- How to determine +/- sign when calculating diagona
- Seaborn HeatMap - How to set colour grading throug
- Direction of tick marks in matplotlib
- Adjacency list with O(1) look up time using HashSe
- Broken axis in Google charts
相关文章
- how to flatten input in `nn.Sequential` in Pytorch
- Mercurial Commit Charts / Graphs [closed]
- What are the problems associated to Best First Sea
- Looping through training data in Neural Networks B
- Sankey diagrams in Python
- Java: Traveling Salesman - Found polynomial algori
- Which computer vision library & algorithm(s), for
- Generating a Voronoi Diagram around 2D Polygons
Compilation of other answers by NotAUser, dreaMone and Bruno Calza
Dijkstra's Algorithm finds the shortest path from the root node to every other node. uniform cost searches for shortest paths in terms of cost from the root node to a goal node. Uniform Cost Search is Dijkstra's Algorithm which is focused on finding a single shortest path to a single finishing point rather than the shortest path to every point.
UCS does this by stopping as soon as the finishing point is found. For Dijkstra, 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.
UCS has fewer space requirements, where the priority queue is filled gradually as opposed to Dijkstra's, which adds all nodes to the queue on start with an infinite cost.
As a result of the above points, Dijkstra is more time consuming than UCS
UCS is usually formulated on trees while Dijkstra is used on general graphs
Djikstra is only applicable in explicit graphs where the entire graph is given as input. UCS starts with the source vertex and gradually traverses the necessary parts of the graph. Therefore, it is applicable for both explicit graphs and implicit graphs (where states/nodes are generated).
http://en.wikipedia.org/wiki/Uniform-cost_search#Relationship_to_other_algorithms
Dijkstra's algorithm searches for shortest paths from root to every other node in a graph, whereas uniform-cost searches for shortest paths in terms of cost to a goal node.
Also, uniform cost has less space requirements, whereas the priority queue is filled "lazily" opposed to Dijkstra's, which adds all nodes to the queue on start with an infinite cost.
There's a paper that talk about the similarities and differences about both.
http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357