An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
From MaRDI portal
Publication:3801096
DOI10.1137/0216065zbMath0654.68088MaRDI 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 complexity; random graphs; all pairs shortest path; weighted directed graph; heap; average time; endpoint independent graphs
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
Related Items
Finding real-valued single-source shortest paths in o(n 3) expected time, Unnamed Item, A Forward-Backward Single-Source Shortest Paths Algorithm, Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time, On the all-pairs shortest path algorithm of Moffat and Takaoka, Average update times for fully-dynamic all-pairs shortest paths, Average-case complexity of the min-sum matrix product problem, Constructing minimum-interference networks, A new upper bound on the complexity of the all pairs shortest path problem, Shortest path algorithms for nearly acyclic directed graphs, All-pairs shortest paths and the essential subgraph, Computation of shortest path in cellular automata, A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time, Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem
