grfloyd.c

来自「经典c++程序的实现」· C语言 代码 · 共 17 行

void Floyd(Graph &G) {        // Compute all-pairs shortest paths
  int D[4][4];
//  int D[G.n()][G.n()];        // Store distances
/*  int **D;
  D = new int [G.n()][G.n()];
*/
  for (int i=0; i<G.n(); i++) // Initialize D with weights
    for (int j=0; j<G.n(); j++)
      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][j] > (D[i][k] + D[k][j]))
          D[i][j] = D[i][k] + D[k][j];
}