floyd.h

来自「包含各种测试,查找和算法等代码,如冒泡算法,树的遍历,链表,队列,堆栈等」· C头文件 代码 · 共 64 行

#include <conio.h>
void Floyd(AdjMWGraph &G, int **distance, int **path)
//求图G中每对顶点之间的最短距离distance和最短路径的顶点序号path
{
	int i, j, k;
	int n = G.NumOfVertices();
   
	//初始化
	for(i = 0; i < n; i++) 
		for(j = 0; j < n; j++)
		{
			distance[i][j] = G.GetWeight(i, j);
			if(i != j && distance[i][j] != MaxWeight) 
				path[i][j] = i;
			else if(i == j) 
				path[i][j] = 0;
			else path[i][j] = -1;
		}

		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
				cout << distance[i][j] << "   ";
			cout << endl;
		}
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
				cout << path[i][j] << "   ";
			cout << endl;
		}
		cout << endl;
		getch();

		
	for(k = 0; k < n; k++)
	{
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
			{
				if(distance[i][j] > (distance[i][k] + distance[k][j]))
				{
					distance[i][j] = distance[i][k] + distance[k][j];
					path[i][j] = path[k][j];
				}
			}
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
				cout << distance[i][j] << "   ";
			cout << endl;
		}
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
				cout << path[i][j] << "   ";
			cout << endl;
		}
		cout << endl;
		getch();
	}
}