An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
From MaRDI portal
Publication:3801096
DOI10.1137/0216065zbMath0654.68088OpenAlexW2054523876MaRDI QIDQ3801096
Tadao Takaoka, Alistair Moffat
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216065
computational complexityrandom graphsall pairs shortest pathweighted directed graphheapaverage timeendpoint independent graphs
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Related Items (16)
Unnamed Item ⋮ All-pairs shortest paths and the essential subgraph ⋮ Computation of shortest path in cellular automata ⋮ On the all-pairs shortest path algorithm of Moffat and Takaoka ⋮ Average-case complexity of the min-sum matrix product problem ⋮ A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time ⋮ An efficient parallel algorithm for the all pairs shortest path problem ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Constructing minimum-interference networks ⋮ Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem ⋮ Finding real-valued single-source shortest paths in o(n 3) expected time ⋮ A new upper bound on the complexity of the all pairs shortest path problem ⋮ Shortest path algorithms for nearly acyclic directed graphs ⋮ Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
This page was built for publication: An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
