图：FLoyd算法

#include  
#include
#include
using namespace std;
#define MAXWEIGHT 100
#undef INFINITY
#define INFINITY 1000
class Graph
{
private:
	//顶点数  
	int numV;
	//边数  
	int numE;
	//邻接矩阵  
	int **matrix;
public:
	Graph（int numV）;
	//建图  
	void createGraph（int numE）;
	//析构方法  
	~Graph（）;
	//Floyd算法
	void Floyd（）;
	//打印邻接矩阵  
	void printAdjacentMatrix（）;
	//检查输入  
	bool check（int int int）;
};
//构造函数，指定顶点数目
Graph::Graph（int numV）
{
	//对输入的顶点数进行检测
	while （numV <= 0）
	{
		cout << “顶点数有误！重新输入 “;
		cin >> numV;
	}
	this->numV = numV;
	//构建邻接矩阵，并初始化
	matrix = new int*[numV];
	int i j;
	for （i = 0; i < numV; i++）
		matrix[i] = new int[numV];
	for （i = 0; i < numV; i++）
	for （j = 0; j < numV; j++）
	{
		if （i == j）
			matrix[i][i] = 0;
		else
			matrix[i][j] = INFINITY;
	}
}
void Graph::createGraph（int numE）
{
	/*
	对输入的边数做检测
	一个numV个顶点的有向图，最多有numV*（numV - 1）条边
	*/
	while （numE < 0 || numE > numV*（numV - 1））
	{
		cout << “边数有问题！重新输入 “;
		cin >> numE;
	}
	this->numE = numE;
	int tail head weight i;
	i = 0;
	cout << “输入每条边的起点（弧尾）、终点（弧头）和权值“ << endl;
	while （i < numE）
	{
		cin >> tail >> head >> weight;
		while （!check（tail head weight））
		{
			cout << “输入的边不正确！请重新输入 “ << endl;
			cin >> tail >> head >> weight;
		}
		matrix[tail][head] = weight;
		i++;
	}
}
Graph::~Graph（）
{
	int i;
	for （i = 0; i < numV; i++）
		delete[] matrix[i];
	delete[]matrix;
}
/*
弗洛伊德算法
求各顶点对之间的最短距离
及其路径
*/
void Graph::Floyd（）
{
	//为了不修改邻接矩阵，多用一个二维数组
	int **Distance = new int*[numV];
	int i j;
	for （i = 0; i < numV; i++）
		Distance[i] = new int[numV];
	//初始化
	for （i = 0; i < numV; i++）
	for （j = 0; j < numV; j++）
		Distance[i][j] = matrix[i][j];

	//prev数组
	int **prev = new int*[numV];
	for （i = 0; i < numV; i++）
		prev[i] = new int[numV];
	//初始化prev
	for （i = 0; i < numV; i++）
	for （j = 0; j < numV; j++）
	{
		if （matrix[i][j] == INFINITY）
			prev[i][j] = -1;
		else
			prev[i][j] = i;
	}
	
	int d v;
	for （v = 0; v < numV; v++）
	for （i = 0; i