6
$\begingroup$

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?

$\endgroup$

1 Answer 1

9
$\begingroup$

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}
$\endgroup$
5
  • $\begingroup$ Thanks. But what do you mean it appears "implicitly". Do you mean it isn't really there in memory, just in spirit? $\endgroup$ Apr 16, 2022 at 23:56
  • $\begingroup$ Also, I'm surprised they didn't mention that $S$ is redundant in either the text or the exercises. $\endgroup$ Apr 16, 2022 at 23:58
  • 1
    $\begingroup$ An explicit appearance will be a variable that is $S$. An implicit appearance could be like right after for each vertex v in G.Adj[u]: RELAX(u,v,w)), let v.d=-v.d so that a vertex is settled iff the distance to it is nonpositive, assuming all edge weights are positive. This implicit appearance might save some memory. $\endgroup$
    – John L.
    Apr 17, 2022 at 0:15
  • 3
    $\begingroup$ The authors of CLRS must have been keenly aware the redundancy of $S$ in the pseudocode as well as its indispensability for other purposes. It may not be wise to say $S$ is redundant in either the text or the exercises. In every tutorial about Dijkstra's algorithm, set $S$ or the concept it represents should appear. $\endgroup$
    – John L.
    Apr 17, 2022 at 0:25
  • $\begingroup$ Thanks, this helps a ton! $\endgroup$ Apr 17, 2022 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.