# Dijkstra without decrease key

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.

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?

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].
• @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. Dec 13, 2019 at 13:15
• @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? Dec 15, 2019 at 2:28