/* *** ODSATag: Floyd *** */
/** Compute all-pairs shortest paths */
static void Floyd(Graph G, int[][] D) {
  for (int i=0; i<G.n(); i++) { // Initialize D with weights
    for (int j=0; j<G.n(); j++) {
      if (G.weight(i, j) != 0) { D[i][j] = G.weight(i, j); }
    }
  }
  for (int k=0; k<G.n(); k++) { // Compute all k paths
    for (int i=0; i<G.n(); i++) {
      for (int j=0; j<G.n(); j++) {
        if ((D[i][k] != Integer.MAX_VALUE) &&
            (D[k][j] != Integer.MAX_VALUE) &&
            (D[i][j] > (D[i][k] + D[k][j])))
            {
          D[i][j] = D[i][k] + D[k][j];
            }
          }
        }
      }
}
/* *** ODSAendTag: Floyd *** */