What's the difference between uniform-cost sea

2019-03-08 22:41发布

I was wondering what's the difference between uniform-cost search and Dijkstra's algorithm. They seem to be the same algorithm.

4条回答
贪生不怕死
2楼-- · 2019-03-08 23:30

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).

查看更多
走好不送
3楼-- · 2019-03-08 23:32

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

http://en.wikipedia.org/wiki/Uniform-cost_search#Relationship_to_other_algorithms

查看更多
不美不萌又怎样
4楼-- · 2019-03-08 23:47

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.

查看更多
看我几分像从前
5楼-- · 2019-03-08 23:47

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

查看更多
登录 后发表回答