An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
Authors:
- Alistair MoffatAMAlistair Moffat
- Tadao TakaokaTTTadao Takaoka
- 1 December 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 16 (6) , 1023-1031
Abstract
An algorithm is described that solves the all pairs shortest path problem for a nonnegatively weighted directed graph of n vertices in average time $O(n^2 \log n)$. The algorithm is a blend of two previous shortest path algorithms, those of Dantzig [Management Sci., 6 (1960), pp. 187–190] and Spira [SIAM J. Comput., 2 (1973), pp. 28–32]. Bloniarz [SIAM J. Comput., 12 (1983), pp. 588–600] categorised a class of random graphs called endpoint independent graphs; the new algorithm executes in the stated time on endpoint independent graphs and represents an asymptotic improvement over the $O(n^2 \log n\log ^ * n)$ algorithm given by Bloniarz for this class of random graphs.
Keywords
This publication has 10 references indexed in Scilit:
- The shortest-path problem for graphs with random arc-lengthsDiscrete Applied Mathematics, 1985
- An all pairs shortest path algorithm with expected running time O(n 2logn)1985
- A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$SIAM Journal on Computing, 1983
- A Note on Spira’s Algorithm for the All-Pairs Shortest-Path ProblemSIAM Journal on Computing, 1977
- New Bounds on the Complexity of the Shortest Path ProblemSIAM Journal on Computing, 1976
- On the decision tree complexity of the shortest path problems1975
- A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$SIAM Journal on Computing, 1973
- Algorithm 97: Shortest pathCommunications of the ACM, 1962
- On the Shortest Route Through a NetworkManagement Science, 1960
- A note on two problems in connexion with graphsNumerische Mathematik, 1959