Answers.Body: <p>The answer to my question can be found in the paper <a href="https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357" rel="nofollow noreferrer">Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm</a> (2011), in particular section <strong>Similarities of DA and UCS</strong>, so you should read this paper for all the details.</p>
  <p>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 <em>single-source</em> DA and UCS is that, in DA, <strong>all</strong> nodes are initially inserted in a priority queue, while in UCS nodes are inserted lazily.</p>
  <p>Here is the pseudocode (taken from the cited paper) of DA</p>
  <p><a href="https://i.sstatic.net/OXoFf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/OXoFf.png" alt="enter image description here" /></a></p>
  <p>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 <span class="math-container">$g(n)$</span> is the cost of the path from the source node to <span class="math-container">$n$</span> (although the title indicates that this is the pseudocode of BFS).</p>
  <p><a href="https://i.sstatic.net/nFxKH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nFxKH.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-30T21:42:11.560Z
Answers.Text: 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.
Answers.UserDisplayName: mic
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-30T23:07:07.080Z
Answers.Text: @mic Well, here, I'm comparing the conventional Dijkstra's algorithm with UCS. I will maybe take a look at the other variants later.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-17T12:56:31.920Z
Answers.LastActivityDate: 2020-11-17T12:56:31.920Z
Answers.UserDisplayName: nbro
Answers.Body: <p>@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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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 &quot;inf&quot; 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</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T19:46:50.393Z
Answers.LastActivityDate: 2023-10-10T08:18:29.140Z
Answers.LastEditDate: 2023-10-10T08:18:29.140Z
Answers.UserDisplayName: Chengfei Wang
Body: <p>Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path <strong>Dijkstra's algorithm (DA)</strong>. If you also took an introductory course on artificial intelligence (<a href="https://ai.stackexchange.com/q/2514/2444">as I did a few years ago, during my bachelor's</a>), you should have also encountered some search algorithms, in particular, the <strong>uniform-cost search (UCS)</strong>.</p>
  <p>A few articles on the web (such as <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow noreferrer">the Wikipedia article on DA</a>) say that DA (or a variant of it) is equivalent to the UCS. The famous Norvig and Russell's book <em>Artificial Intelligence: A Modern Approach</em> (3rd edition) even states</p>
  <blockquote>
  <p>The two-point shortest-path algorithm of <a href="http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf" rel="nofollow noreferrer">Dijkstra (1959)</a> is the origin of uniform-cost search. These works also introduced the idea of explored and frontier sets (closed and open lists).</p>
  </blockquote>
  <p>How exactly is DA equivalent to UCS?</p>
  
Tags: <comparison><search><uniform-cost-search><dijkstras-algorithm><shortest-path-problem>
Title: What is the difference between the uniform-cost search and Dijkstra's algorithm?
UserDisplayName: nbro
ThreadText: # What is the difference between the uniform-cost search and Dijkstra's algorithm?
  
  (Asked by: username_0 on 2020-11-17)
  
  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](https://ai.stackexchange.com/q/2514/2444)), 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](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)) 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)](http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf) 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?
  
  **Tags:** comparison, search, uniform-cost-search, dijkstras-algorithm, shortest-path-problem
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2020-11-17. Score: 1 | Accepted answer
  
  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](https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357) (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](https://i.sstatic.net/OXoFf.png)](https://i.sstatic.net/OXoFf.png)
  
  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](https://i.sstatic.net/nFxKH.png)](https://i.sstatic.net/nFxKH.png)
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: @mic Well, here, I'm comparing the conventional Dijkstra's algorithm with UCS. I will maybe take a look at the other variants later.  
  
  ---
  
  ### Answer by username_2 on 2023-09-04. Score: 0
  
  @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
  
  
  ---
  
  