4
$\begingroup$

I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new nodes. Please see the pseudo code listed on the right-hand side below, which is taken from page 16 of that paper.

Dijkstra's algorithm pseudocode from the paper

But to me the code looks wrong. I think the comparison should be

k <= d[u]

and also the update of the d[u] in the next line seems redundant to me. I think the delete-min operation can never return a vertex with distance label k which is strictly less than d[u] since whenever a vertex distance pair is inserted into the priority queue the distance array d is updated. Am I correct in assuming that this is a mistake in the paper?

$\endgroup$

1 Answer 1

3
$\begingroup$

You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary.

The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] holds when (u,k) is picked up from the queue. Moreover, if d[u] is strictly smaller than k , the element should simply be ignored since it cannot be the shortest path to u.

You can change the condition to k == d[u] and remove following update to d[u].

$\endgroup$
9
  • $\begingroup$ I don’t think one should remove the if statement completely. If if one pulls a “dead” node out of the queue looping over its neighbors is unnecessary. $\endgroup$ Dec 13, 2019 at 12:10
  • $\begingroup$ @user3726947 I wonder what node should be considered "dead." When minimum one is pulled from the queue, its k value is equal to d[u] so it seems worth visiting its neighbors. $\endgroup$
    – Ryoji
    Dec 13, 2019 at 13:15
  • $\begingroup$ I don’t think that’s true. Note that each time a better path to some vertex is found the vertex distance pair is inserted into the heap. Have a look at the algorithm on the right on page 16. So it might happen that a vertex has a worse distance than the optimal one recorded in the array d. $\endgroup$ Dec 14, 2019 at 11:18
  • $\begingroup$ @user3726947 I got your point. The queue contains the "dead" entry, i.e. one whose distance value is greater than optimal distance in d. That happen after optimal one is pulled and d is updated. Remaining queue entries for the same vertex should be considered dead after minimum one is processed. So should the IF statement be k == d[u] removing the update on the next line? $\endgroup$
    – Ryoji
    Dec 15, 2019 at 2:28
  • $\begingroup$ I just updated the answer. Thanks for the feedback. $\endgroup$
    – Ryoji
    Dec 18, 2019 at 20:10

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.