Efficient parallel algorithms for computing all pair shortest paths in directed graphs
Yijie Han, Victor Ya. Pan, John H. Reif · 1992
recursive steps in the worst case and thus require at least the order of n time in their parallel im-We present parallel algorithms for computing all plementation, even if the number of available propair shortest paths in directed graphs.Our algocessors is not bounded.O(n) time and n2 procesrithm has time complexity O(j(n)/p + l(n) log n) sor bounds can indeed be achieved, for inst ante, on the PRAM using p processors, where I(n) is in the straightforward parallelization of the algolog non the EREW PRAM, log log n on the CRCW rithm of [Fl].(Here and hereafter we assume the PRAM, ~(n) is o(n3).On the randomized CRCW customary PRAM models of parallel computing PRAM we are able to achieve time complexity [KR].)0(n3/p + iog n) using p processors.NC algorithms are also available for this problem.However, they either need O(n3 log n) ope-