A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
Author:
- Peter A. BloniarzPBPeter A. Bloniarz
- 1 August 1983
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 12 (3) , 588-600
Abstract
We present an algorithm which determines the shortest distances between all pairs of points in a nonnegatively weighted directed graph in average time $O(n^2 \log n\log ^ * n)$. This algorithm, which uses a search strategy similar to Dantzig [Management Sci., 2 (1960), pp. 187–190; Linear Programming and Extensions, Princeton Univ. Press, 1963] and Spira [SIAM J. Comput., 2 (1973), pp. 28–32] executes in the stated time over quite general classes of probability distributions on such graphs.
Keywords
This publication has 11 references indexed in Scilit:
- Linear expected-time algorithms for connectivity problemsJournal of Algorithms, 1980
- Implementing Quicksort programsCommunications of the ACM, 1978
- An Algorithm for Transitive Closure with Linear Expected TimeSIAM Journal on Computing, 1978
- 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
- 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
- Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½
N
3
Additions and
N
3
ComparisonsJournal of the ACM, 1972
- 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