The authors present an implementation of a priority queue by k doubly linked lists. Each list contains elements in nondecreasing order of the weights. Searching for the minimal element is reduced to finding the smallest of the list head elements. Updating a weight is realized by deleting the element from the list it is contained in and adding it to an extra chain. The data structure allows update operations and insertions to be carried out in constant time if the elements can be accessed via an additional array of pointers and if the weights of elements changed or inserted between two successive EXTRACTMIN operations form a monotone sequence. Thus, the time complexity of the priority queue algorithm is O(n^l.5+m) with n being the initial size of the queue, and m the number of updates.

In order to show that the assumption can be met in practice, the authors use this data structure to solve the all paris shortest path problem on a directed graph. Their algorithm requires n³+O(n^2.5) operations on edge weights. They acknowledge that Yen’s algorithm [1] will run faster in practice although its bound is 1.5n³. This paper is clearly written. It is especially easy to go through the efficiency considerations. There is a misprint in the proof of Theorem 1: one must read a plus sign instead of the equal sign.