A priority queue for the all pairs shortest path problem
type: Item
instance of: scholarly article
title: A priority queue for the all pairs shortest path problem
zbMATH Open document ID: 0539.68022
DOI: 10.1016/0020-0190(84)90109-1
author: Alistair Moffat
author: Tadao Takaoka
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3858397
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: linked list priority queue data structure
zbMATH Keywords: shortest path algorithm
describes a project that uses: Algorithm 97
describes a project that uses: heapsort
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90109-1
OpenAlex ID: W1991351021
cites work: Q4773298
cites work: A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
cites work: A note on two problems in connexion with graphs
cites work: New Bounds on the Complexity of the Shortest Path Problem
cites work: Q5656786
cites work: Priority queues with update and finding minimum spanning trees
cites work: A note on 'Is shortest path problem not harder than matrix multiplication?'
cites work: Shortest-path problem is not harder than matrix multiplication
cites work: A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
cites work: Q3893329
cites work: Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N 3 Additions and
cites work: An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
Recommended article: The all-pairs quickest path problem
Recommended article: Computing and Combinatorics
Recommended article: Q5289052
Recommended article: Efficient parameterized algorithms for computing all-pairs shortest paths
Recommended article: Q5874311
Recommended article: All-Pairs Almost Shortest Paths
Recommended article: Two fast algorithms for all-pairs shortest paths
Recommended article: A new approach to dynamic all pairs shortest paths
Recommended article: Q5212359
description: scientific article; zbMATH DE number 3858397