Difference between Prim and Dijkstra graph algorithm

Question

I'm reading graph algorithms from Cormen book. Below is pseudocode from that book

Prim algorithm for MST

MST-PRIM (G, w, r)

for each u in G.V
  u.key = infinity
  u.p = NIL

r.key = 0
Q = G.V
while Q neq null
  u = EXTRACT-MIN(Q)
  for each v in G.Adj[u]
    if (v in Q) and (w(u,v) < v.key)
      v.p = u
      v.key = w(u,v)

Dijkstra algorithm to find single source shortest path.

INITIALIZE-SINGLE-SOURCE (G,s)
  for each vertex v in G.V
    v.d = infinity
    v.par = NIL
  s.d = 0

DIJKSTRA (G, w, s)
  INITIALIZE-SINGLE-SOURCE(G,s)
  S = NULL
  Q = G.V
  while Q neq null
    u = EXTRACT-MIN(Q)
    S = S U {u}
    for each vertex v in G.Adj[u]
      RELAX(u,v,w)

My question is, why we are checking if vertex belongs to Q (v in Q), i.e. that vertex doesn't belong to tree, whereas in Dijkstra algorithm we are not checking for that.

Any reason, why?

Answer 1

The algorithms called Prim and Dijkstra solve different problems in the first place. 'Prim' finds a minimum spanning tree of an undirected graph, while 'Dijkstra' solves the single-source shortest path problem for directed graphs with nonnegative edge weights.

Answer 2

In both algorithms queue Q contains all vertices that are not 'done' yet, i.e. white and gray according to common terminology (see here).

In Dijkstra's algorithm, the black vertex cannot be relaxed, because if it could, that would mean that its distance was not correct beforehand (contradicts with property of black nodes). So there is no difference whether you check v in Q or not.

In Prim's algorithm, it is possible to find an edge of small weight, that leads to already black vertex. That's why if we do not check v in Q, then the value in vertex v can change indeed. Normally, it does not matter, because we never read min-weight value for black vertices. However, your pseudocode is using MinHeap data structure. In this case each modification of vertex values must be accompanied with DecreaseKey. Clearly, it is not valid to call DecreaseKey for black vertices, because they are not in heap. That's why I suppose author decided to check for v in Q explicitly.

Speaking generally, the codes for Dijkstra's and Prim's algorithms are usually absolutely same, except for a minor difference:

• Prim's algorithm checks w(u, v) for being less than D(v) in RELAX.
• Dijkstra's algorithm checks D(u) + w(u, v) for being less D(v) in RELAX.