Moffat, Alistair; Takaoka, Tadao A priority queue for the all pairs shortest path problem. (English) Zbl 0539.68022 Inf. Process. Lett. 18, 189-193 (1984). 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 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 J. Y. Yen’s bound [J. Assoc. Comput. Mach. 19, 423-424 (1972; Zbl 0242.94028)] of \((3/2)n^ 3\) operations. MSC: 68W99 Algorithms in computer science 68P05 Data structures 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity Keywords:analysis of algorithms; linked list priority queue data structure; shortest path algorithm Citations:Zbl 0092.160; Zbl 0242.94028 Software:heapsort; Algorithm 97 PDFBibTeX XMLCite \textit{A. Moffat} and \textit{T. Takaoka}, Inf. Process. Lett. 18, 189--193 (1984; Zbl 0539.68022) Full Text: DOI References: [1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029 [2] Bloniarz, P. A., A shortest path algorithm with expected time \(O(n^2 logn log^∗\) n)\), SIAM J. Comput., 12, 588-600 (1983) · Zbl 0521.68078 [3] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002 [4] Floyd, R. W., Algorithm 97: shortest path, Comm. ACM, 5, 345 (1962) [5] Fredman, M. L., New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5, 83-89 (1976) · Zbl 0326.68027 [6] Iri, M.; Nakamori, M., Path sets, operator semigroups and shortest path algorithms on a network, RAAG Res. Notes, 185 (1972), Third series · Zbl 0245.05106 [7] Johnson, D. B., Priority queues with update and finding minimum spanning trees, Inform. Process. Lett., 4, 53-57 (1975) · Zbl 0318.68032 [8] Moran, S., A note on ‘Is shortest path problem not harder than matrix multiplication?’, Inform. Process. Lett., 13, 85-86 (1981) · Zbl 0474.68078 [9] Romani, F., Shortest path problem is not harder than matrix multiplication, Inform. Process. Lett., 11, 134-136 (1980) · Zbl 0454.68069 [10] Spira, P. M., A new algorithm for finding all shortest paths in a graph of positive edges in average time \(O(n^2 log^2n)\), SIAM J. Comput., 2, 28-32 (1973) · Zbl 0254.05118 [11] Takaoka, T.; Moffat, A. M., An \(O(n^2\) log \(n\) log log \(n)\) expected time algorithm for the all shortest distance problem, (Lecture Notes in Comput. Sci., 88 (1980), Springer: Springer Berlin), 643-655 [12] Williams, J. W.J., Algorithm 232: heapsort, Comm. ACM, 7, 347-348 (1964) [13] Yen, J. Y., Finding the lengths of all shortest paths in \(N\)-node nonnegative distance complete networks using \(12N^3 additions and N^3\) comparisons, J. ACM, 19, 423-434 (1972) · Zbl 0242.94028 [14] Yuval, G., An algorithm for findings all the shortest paths using \(N^{2.81}\) infinite precision multiplications, Inform. Process. Lett., 4, 155-156 (1976) · Zbl 0333.68034 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.