12-8.c

来自「数据结构用C语言实现」· C语言 代码 · 共 52 行

#include "stdio.h"
#include "stdlib.h"
typedef int DataType;
void Allpairs(DataType **c, int **kay)
{//所有点对的最短路径
//对于所有i和j，计算c [ i ] [ j ]和k a y [ i ] [ j ]
//初始化c [ i ] [ j ] = c（i，j，0）
	int i,j,k;
	for (i = 1; i <= n; i++)
		for(j = 1; j <= n; j++) 
		{
			c[i][j] = a[i][j];
			kay[i][j] = 0;
		}
	for (i = 1; i <= n; i++)
		c[i][i] = 0;
	// 计算c[i][j] = c(i,j,k)
	for(k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++) {
				DataType t1 = c[i][k];
				DataType t2 = c[k][j];
				DataType t3 = c[i][j];
				if (t1 !=0&& t2 !=0&& (t3 ==0||t1+t2<t3)){
					c[i][j] = t1 + t2;
					kay[i][j] = k;
				}
			}
}
void outputPath(int **kay, int i, int j)
{// 输出i 到j 的路径的实际代码
	if (i == j) 
		return;
	if (kay[i][j] == 0) 
		printf("%d ",j);
	else {
		outputPath(kay,i, kay[i][j]);
		outputPath(kay,kay[i][j],j);
	}
}
//输出最短路径
void PrintPath(DataType **c, int **kay, DataType NoEdge, int i, int j)
{// 输出从i 到j的最短路径
	if (c[i][j] == NoEdge) {
		printf("There is no path from %d to %d\n",i,j);
		return ; 
	}
	printf( "The path is\n");
	printf("%d",i);	
	outputPath(kay,i,j) ;
}