What's the difference between uniform-cost search and Dijkstra's algorithm?

GraphArtificial Intelligence

Graph Problem Overview


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

Graph Solutions


Solution 1 - Graph

> 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

Solution 2 - Graph

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.

Solution 3 - Graph

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

Solution 4 - Graph

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

Solution 5 - Graph

The main difference is that Dijkstra's algorithm is defined when numbers of vertices is finite. It says to put all the vertices in a queue. But we can not put all the vertices in a queue when numbers of vertices tend to infinite. Uniform Cost Search is defined in a situation like this, where numbers of vertices are unknown.

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionGrief CoderView Question on Stackoverflow
Solution 1 - GraphNotAUserView Answer on Stackoverflow
Solution 2 - GraphRobertoRView Answer on Stackoverflow
Solution 3 - GraphVineetNayak28View Answer on Stackoverflow
Solution 4 - GraphBruno CalzaView Answer on Stackoverflow
Solution 5 - Graphayaz8fView Answer on Stackoverflow