A priority queue for the all pairs shortest path problem

DOI10.1016/0020-0190(84)90109-1zbMath0539.68022OpenAlexW1991351021MaRDI QIDQ794155

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 algorithmsshortest path algorithmlinked list priority queue data structure

Mathematics Subject Classification ID

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

Uses Software

• Algorithm 97
• heapsort

Cites Work

• A note on two problems in connexion with graphs
• Shortest-path problem is not harder than matrix multiplication
• A note on 'Is shortest path problem not harder than matrix multiplication?'
• Priority queues with update and finding minimum spanning trees
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• New Bounds on the Complexity of the Shortest Path Problem
• Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N ³ Additions and N ³ Comparisons
• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
• Unnamed Item
• Unnamed Item
• Unnamed Item

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