Dijkstra without decrease key I was reading through this paper, &quot;Priority Queues and Dijkstra's Algorithm&quot; 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 &lt;= 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 &lt; 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 &gt;= 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].