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

Question

Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path Dijkstra's algorithm (DA). If you also took an introductory course on artificial intelligence (as I did a few years ago, during my bachelor's), you should have also encountered some search algorithms, in particular, the uniform-cost search (UCS).

A few articles on the web (such as the Wikipedia article on DA) say that DA (or a variant of it) is equivalent to the UCS. The famous Norvig and Russell's book Artificial Intelligence: A Modern Approach (3rd edition) even states

The two-point shortest-path algorithm of Dijkstra (1959) is the origin of uniform-cost search. These works also introduced the idea of explored and frontier sets (closed and open lists).

How exactly is DA equivalent to UCS?

Answer 1

The answer to my question can be found in the paper Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm (2011), in particular section Similarities of DA and UCS, so you should read this paper for all the details.

DA and UCS are logically equivalent (i.e. they process the same vertices in the same order), but they do it differently. In particular, the main practical difference between the single-source DA and UCS is that, in DA, all nodes are initially inserted in a priority queue, while in UCS nodes are inserted lazily.

Here is the pseudocode (taken from the cited paper) of DA

Here is the pseudocode of the best-first search (BFS), of which UCS is just a particular case. Actually, this is the pseudocode of UCS where $g(n)$ is the cost of the path from the source node to $n$ (although the title indicates that this is the pseudocode of BFS).

Answer 2

@mic Both of you make sense, but Mic's reasoning is more fundamental. Since all other nodes are initially inf in Dijkstra, it actually does not matter if you put them in PQ or not. That is not the real reason.

If you compare AIMA and CLRS textbook pseudocode side by side, you will find that everything is the same except UFS divided the nodes that are unexplored further into two cases during expansion: (1) in frontier unexplored and (2) not in frontier unexplored.

If you don't maintain ALL estimated distances from the source to all other nodes at the beginning, then you have to maintain distances LATER using other methods, and that is exactly how UCS works.

UCS does the following: If not in the frontier (equivalent to inf), then put it into the frontier first, and start tracking its cost from now (equivalent to distance first update, no longer inf). If it is already in the frontier and still unexplored, then update with a shorter value. Since UCS only starts tracking the distance of nodes when they first enter the frontier, they don't need to track ALL node distances with inf at the beginning.

In other words, because Dijkstra chose to track ALL nodes with inf at the beginning, it does not matter whether the unexplored nodes are in the frontier or not anymore, the "inf" just means they are not in the frontier. This also tells us why UCS is always better than Dijkstra: it saves the memory of tracking all nodes, which is particularly useful in the AI when the number of the states are too large