floyd.cpp

C++的电子教程

#include<stdio.h>
#define Max 100
#define I 32767
typedef int Mat[Max][Max];
Mat a,path;

//Floyd 算法函数
void floyd(int cost[][4],int n)
{
	int i,j,k;
	for (i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			a[i][j]=cost[i-1][j-1];
			path[i][j]=0;
		}
	for (k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(a[i][k]+a[k][j]<a[i][j])
				{
					a[i][j]=a[i][k]+a[k][j];   //从顶点i到顶点j的最短路径长度
					path[i][j]=k;              //i到j的一个中间结点
				}
}

//输出从i到j的最短路径的所有中间结点
void print_path(int i,int j)
{
	int k;

	k=path[i][j];
	if (k==0)	return;

	print_path(i,k);
	printf("%d,",k);
	print_path(k,j);
}

//输出n*n阶邻接矩阵表示的带权有向图中的所有最短路径
void print_all_path(int n)
{
	int i,j;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			if (a[i][j]==I)
				printf("从顶点%d到顶点%d没有路径!\n",i,j);
			else
				if (i!=j)
				{
					printf("从顶点%d到顶点%d的路径为",i,j);
					printf("<%d,",i);
					print_path(i,j);   //输出i到j最短路径的中间结点
					printf("%d> ",j);
					printf(", 其长度为%d。\n",a[i][j]);
				}
		}
}
//主函数
void main()
{
	int cost[][4]={	{0,1,I,4},	
					{I,0,9,2},
					{3,5,0,8},	
					{I,I,6,0} };
    int	n=4; 
	floyd(cost,n);
	print_all_path(n);
}