12-9.c

单源最短路径求解

图的构造与单源最短路径的求解及其性能分析
#include "stdio.h"
#include "stdlib.h"
typedef int DataType;
void Allpairs(DataType **c, int **kay)
{//所有点对的最短路径
//对于所有i和j，计算c[i][j]和kay[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) ;
}