c++实现最短路径弗洛伊德算法

#include 
using namespace std;
#define MAXVEX 9 //最大顶点数
#define INFINITY 65535 //极大值  即无穷

typedef struct
{
	string vexs[MAXVEX]; //顶点表
	int arc[MAXVEX][MAXVEX]; //邻接矩阵，可看做边表
	int numNodes, numEdges; // 图中当前的顶点数和边数
}MGraph;

void CreateMGraph(MGraph& G)
{
	int i, j, k, w;
	cout << "请输入顶点数和边数" << endl;
	cin >> G.numNodes >> G.numEdges;
	for (i = 0; i < G.numNodes; i++) //建立顶点表
	{
		cout << "请输入顶点值" << endl;
		cin >> G.vexs[i];
	}
	for (i = 0; i < G.numNodes; i++)
	{
		for (j = 0; j < G.numNodes; j++)
		{
			G.arc[i][j] = INFINITY;  //邻接矩阵初始化
			G.arc[i][i] = 0;
		}
	}
	for (k = 0; k < G.numEdges; k++)  //建立邻接矩阵
	{
		cout << "请输入边（vi，vj）上的下标i，下标j和权" << endl;  //输入边上的权
		cin >> i >> j >> w;
		G.arc[i][j] = w;
		G.arc[j][i] = G.arc[i][j];  //无向图中矩阵对称
	}
}

typedef int Patharc[MAXVEX][MAXVEX];  //用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX][MAXVEX];  //用于存储到各点最短路径的权值和

void ShortestPath_Floyd(MGraph G, Patharc P, ShortPathTable D)
{
	int v, w, k;
	for (v = 0; v < G.numNodes; ++v)  //初始化
	{
		for (w = 0; w < G.numNodes; ++w)
		{
			D[v][w] = G.arc[v][w];  
			P[v][w] = w;
		}
	}
	for (k = 0; k < G.numNodes; ++k)
	{
		for (v = 0; v < G.numNodes; ++v)
		{
			for (w = 0; w < G.numNodes; ++w)
			{
				if (D[v][w] > D[v][k] + D[k][w])  //如果经过下标为k顶点的路径比原两点间路径更短
				{
					D[v][w] = D[v][k] + D[k][w];  
					P[v][w] = P[v][k];  //路径设置为下标为k的顶点
				}
			}
		}
	}
	cout << endl;
	cout << "最短路径权值和二维数组如下" << endl;
	for (v = 0; v < G.numNodes; v++)
	{
		for (w = 0; w < G.numNodes; w++)
		{
			cout << D[v][w] << "t";
		}
		cout << endl;
	}
	cout << endl;
	cout << "最短路径下标二维数组如下" << endl;
	for (v = 0; v < G.numNodes; v++)
	{
		for (w = 0; w < G.numNodes; w++)
		{
			cout << P[v][w] << "t";
		}
		cout << endl;
	}
}

int main()
{
	MGraph G;
	CreateMGraph(G);
	Patharc P;
	ShortPathTable D;
	ShortestPath_Floyd(G, P, D);
	system("pause");
	return 0;
}