Go backward to PRAM Variants Go up to Top Go forward to Complexity of MIN |
AllPairsShortestPaths(W): D = W for i=1 to s do D = MatMin(D, D) return D MatMin(D, W): for i=1 to n do in parallel for j=1 to n do in parallel for k=1 to n do in parallel M[i,j,k] = min(D[i,j], D[i,k]+W[k,j]) E[i,j] = MIN(M[i,j]) return EMIN computes minimum of $n$ values.