What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?

Question

I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such that $w(u,v)$ gives you the weight of the edge from $u$ to $v$.

DIJKSTRA(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G,s)
  S = {}
  # Put all vertices of G in a priority queue, Q.
  Q = G.V
  while Q != {}
    u = EXTRACT-MIN(Q)
    S = S U {u}
    for each vertex v in G.Adj[u]:
       RELAX(u,v,w)

Here, the INITIALIZE-SINGLE-SOURCE method simply sets the shortest distance values for $s$ to $0$ and all other vertices to $\infty$. The RELAX method:

RELAX(u,v,w)
  if v.d > u.d + w(u,v)
    v.d = u.d + w(u,v)
    v.pi = u

Note that all vertices have the $v.d$ property which is the length of the shortest path from $s$ to $v$ and the $v.pi$ property which is the parent of $v$ in the shortest path.

Staring at the algorithm, I'm wondering what role the set $S$ is playing exactly. What if I removed $S$ completely - doesn't seem like it'll affect the algorithm at all. What am I missing?

Answer 1

No, you are not missing anything if you remove $S$ completely. You could implement and run Dijkstra's algorithm correctly still.

Set $S$ is used later in the book to help explain the algorithm and prove its correctness.

• $S$ is the set of "settled vertices", the vertices to which the shortest distances from the source have been computed. The partition of all vertices into "settled vertices" and "unsettled vertices" together with the continual settlement of the nearest unsettled vertex summarizes Dijkstra's algorithm.
• The correctness of the algorithm is proved by showing the loop invariant that all vertices in $S$ are settled at the start of each iteration of the while loop.

In most implementations of Dijkstra's algorithm, $S$ does not appear explicitly as a variable or an indicator variable, as you might have suspected. However, it appears implicitly since it consists of all vertices that have been extracted from the priority queue $Q$,

There is a common implementation of the algorithm where $S$ is maintained explicitly, which I have used many times. Since it may not be easy to update the priority of an element in a priority queue efficiently, vertices with shorter distance found are added to the priority queue even if they are in the priority queue. After extracted from priority queue, a vertex will be used to relax the distance of its neighbors only if it is not in $S$, after which it will be added to $S$. Here is the pseudocode.

DIJKSTRA(G, w, s)
   INITIALIZE-SINGLE-SOURCE(G,s)
   S = {}
   # Initialize priority queue Q with the source 
   Q = {s}
   while Q != {}
       u = EXTRACT-MIN(Q)
       if u is not in S
           for each vertex v in G.Adj[u]
               RELAX(u, v, w)
               Add v to Q if v.d becomes less
           S = S U {u}