ON THE EXPONENT OF THE ALL PAIRS SHORTEST-PATH PROBLEM

The upper bound on the exponent, omega, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 19 86 it has been 2.376. On the other hand, the exponent of the algorithm s known for the all pairs shortest path problem has stayed al three al l these years even for the very special case of directed graphs with u niform edge lengths. In this paper we give an algorithm of rime O(n(nu ) log(3) n) v = (3 + omega)/2, for the case of edge lengths in {-1, 0, 1}. Thus, for the current known bound on w, we get a bound on the exp onent, v < 2.688. In case of integer edge lengths with absolute Value bounded above by M, the time bound is O((Mn)(v) log(3) n) and the expo nent is less than 3 for M = O(n(a)) for a < 0.216 and the current boun den omega. (C) 1997 Academic Press.