Go backward to Construction Go up to Top Go forward to Observation

Sequential Algorithm

AllPairsShortestPaths(W):
  D = W
  for i=1 to n-1 do
    D = MatMin(D, W)
  return D

MatMin(D, W):
  for i=1 to n do
    for j=1 to n do
      E[i,j] = D[i,j]
      for k=1 to n do
        E[i,j] = min(E[i,j],D[i,k]+W[k,j])
  return E