A priority queue for the all pairs shortest path problem

DOI10.1016/0020-0190(84)90109-1MaRDI QIDQ794155zbMATH OpenOpenAlexFDO

Authors Alistair Moffat, Tadao Takaoka

Publication date 1984

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(84)90109-1

zbMATH Keywords

analysis of algorithmslinked list priority queue data structureshortest path algorithm

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

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.

Recommendations

• The all-pairs quickest path problem
• Computing and Combinatorics
• scientific article; zbMATH DE number 278831
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Efficient parameterized algorithms for computing all-pairs shortest paths
• All-Pairs Almost Shortest Paths
• Two fast algorithms for all-pairs shortest paths
• A new approach to dynamic all pairs shortest paths
• An all pairs shortest path algorithm for dynamic graphs

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)
• A note on 'Is shortest path problem not harder than matrix multiplication?'
• A note on two problems in connexion with graphs
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N ³ Additions and
• scientific article; zbMATH DE number 3700238 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3387374 (Why is no real title available?)
• New Bounds on the Complexity of the Shortest Path Problem
• Priority queues with update and finding minimum spanning trees
• Shortest-path problem is not harder than matrix multiplication

Cited in

(2)

• Two-Level Heaps: A New Priority Queue Structure with Applications to the Single Source Shortest Path Problem
• Variable-priority queue and doughnut routing

Describes a project that uses

Uses Software

• Algorithm 97
• heapsort

This page was built for publication: A priority queue for the all pairs shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794155)