A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
From MaRDI portal
Publication:5668831
DOI10.1137/0202004zbMath0254.05118OpenAlexW2027580688MaRDI QIDQ5668831
Publication date: 1973
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0202004
Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items (18)
The shortest-path problem for graphs with random arc-lengths ⋮ Unnamed Item ⋮ All-pairs shortest paths and the essential subgraph ⋮ Intelligent transportation systems -- Enabling technologies ⋮ 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 ⋮ Discrete extremal problems ⋮ An algorithm to evaluate public transportation stops for minimizing passenger walking distance ⋮ Finding real-valued single-source shortest paths in o(n 3) expected time ⋮ On the expected behaviors of the Dijkstra's shortest path algorithm for complete graphs ⋮ An algorithm for drawing general undirected graphs ⋮ A bidirectional shortest-path algorithm with good average-case behavior ⋮ A priority queue for the all pairs shortest path problem ⋮ 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: A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
