A priority queue for the all pairs shortest path problem (Q794155)

A linked list priority queue data structure is given that in some situations out performs, in terms of comparisons amongst elements in the data structure, existing priority queue structures such as the heap. It is shown that this new queue structure is suitable for use with \textit{E. W. Dijkstra's} shortest path algorithm [Numer. Math. 1, 269-271 (1959; Zbl 0092.160)] with the combination yielding an algorithm for the all pairs shortest path problem that on a dense graph of n vertices requires \(n^ 3+O(n^{2.5})\) operations on path costs. In a computational framework where addition and comparison are the only operations permitted on path costs, this slightly improves \textit{J. Y. Yen's} bound [J. Assoc. Comput. Mach. 19, 423-424 (1972; Zbl 0242.94028)] of \((3/2)n^ 3\) operations.