What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

Question

I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the current node, and $\rm{}INITIALIZE\rm{-}SINGLE\rm{-}SOURCE(G,s)$ also initialize all $v.\pi=NIL,$ so if it's impossible to reach some node, a simple check $$\textrm{if }v.\pi==NIL$$ is enough. So why the $S$ is needed? If all node can be reached then $S=G.V$ and it will be useless...

Edit: I add the book statement, but I wonder since that the priority queue has been used, the description becomes inconsistent with the pseudocode follows, no need to refer to $V-S$, which will slow down the algorithm?

Edit2: I suspect that priority queue is not a requirement of dijkstra SP algorithm, it's just a technique to speed up it, so the pseudocode in my another question on Dijkstra's SP algorithm is correct?

Edit3: Now I got stuck on my own comment, I suspect it's not correct:

• 

  I tried to make use of $S$, so I tried $G.Adj[u]\color{blue}{-S}$ and thought it will speed up the updating, but what if the following happen that the edge $(\color{red}{v,u})$ will not be selected since $\color{blue}S$ is already subtracted?

  • 

---

Book: Introduction to Algorithm 3ed. page 658, (forget about the679 is just pdf reader page #.)

Answer 1

Yes, the set $S$ is not needed in the Dijkstra’s algorithm, which is at the beginning of section 24.3, Dijkstra’s algorithm of the book introduction to algorithms by CLRS, third edition. That is, line 2 and line 6 in procedure DIJKSTRA($G,w,s$) can be removed without affecting the algorithm.

One immediate purpose of $S$ is to facilitate the proof of theorem 24.6 (Correctness of Dijkstra’s algorithm) of the book. Also, other implementations of Dijktra's might use that set more visibly such as the set of visited nodes in Wikipedia's entry. It is indeed a cornerstone concept to understand Dijktra's algorithm.

By the way, your observation that the line 7 of line 7 could be improved to "for each vertex $v \in G.Adj[u]\setminus S$" is very nice. In fact, that is done in the Wikipedia' entry mentioned above. Should that be done, $S$ could not be removed any more as you have emphasized.