\"\" \"\" \"\"
Go backward to PRAM Variants
Go up to Top
Go forward to Complexity of MIN
RISC-Linz logo

PRAM Program

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 E
MIN computes minimum of n values.
Author: Wolfgang Schreiner
Last modification: November 15, 1996