grfloyd.cpp

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

#include <stdio.h>
#include <iostream.h>
#include <assert.h>

#include "..\..\include\book.h"

#include "..\..\include\grmat.h"

void Floyd(Graph &G) {        // Compute all-pairs shortest paths
  int D[4][4];
  int pre[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);
	  if (D[i][j] != INFINITY && i != j)
	    pre[i][j] = i;
	  else pre[i][j] = -1;
	}
  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];
		  pre[i][j] = k;
		}
/*    for (i=0; i<G.n(); i++)  {
      for (int j=0; j<G.n(); j++) 
          cout << "(" << D[i][j] << "," << pre[i][j] << ")";
	  cout << endl;
	}
*/
    for (i=0; i<G.n(); i++)  {
      for (int j=0; j<G.n(); j++) 
          cout << D[i][j] << " ";
	  cout << endl;
	}
	cout << endl;
    for (i=0; i<G.n(); i++)  {
      for (int j=0; j<G.n(); j++) 
          cout << pre[i][j] << " ";
	  cout << endl;
	}
	cout << endl;
	cout << endl;
  }
}