A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$

DOI10.1137/0212039zbMath0521.68078OpenAlexW2084623271MaRDI QIDQ3670595

Peter A. Bloniarz

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0212039

zbMATH Keywords

shortest pathexpected timeaverage timenonnegatively weighted directed graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Unnamed Item, All-pairs shortest paths and the essential subgraph, Shortest paths in random weighted graphs, 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, Unnamed Item, Finding real-valued single-source shortest paths in o(n 3) expected time, A priority queue for the all pairs shortest path problem, A Forward-Backward Single-Source Shortest Paths Algorithm, Shortest paths in networks with vector weights, Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time