A lower bound for the shortest path problem
K. Mulmuley, P. Shah · 2002
We show that the shortest path problem cannot be solved in o(log n) time on an unbounded fan-in PRAM without bit operations using poly(n) processors even when the bit-lengths of the weights on the edges are restricted to be of size O(log/sup 3/ n). This shows that the matrix-based repeated squaring algorithm for the shortest path problem is optimal in the unbounded fan-in PRAM model without bit operations.