2

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?

nbro
  • 39,006
  • 12
  • 98
  • 176

1 Answers1

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

enter image description here

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

enter image description here

nbro
  • 39,006
  • 12
  • 98
  • 176
  • Dijkstra doesn't need to involve adding all the vertices to the priority queue at the start. See the alternatives at https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue which don't involve a "decrease priority" operation. I think the difference is that uniform-cost search does not maintain a map between nodes and their distance from the source, and terminates when you find the target node. – mic Dec 30 '20 at 21:42
  • @mic Well, here, I'm comparing the conventional Dijkstra's algorithm with UCS. I will maybe take a look at the other variants later. – nbro Dec 30 '20 at 23:07