nshortpath.c

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

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);
			Path[i][j] = 0;
		}

	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] = k;
				}
}