555.cpp

按动态规划余利解决计算图的任意两点见的距离的Floyd算法

#include <iostream.h>
#include <stdlib.h>
#define n 10

void main()
{
	int i,j,k;
	int c[n][n]={{0,99,8,7,6,5,4,3,2,1},{99,0,99,8,7,6,5,4,3,2},
				{8,99,0,99,8,7,6,5,4,3},{7,8,99,0,99,8,7,6,5,4},
				{6,7,8,99,0,99,8,7,6,5},{5,6,7,8,99,0,99,8,7,6},
				{4,5,6,7,8,99,0,99,8,7},{3,4,5,6,7,8,99,0,99,8},
				{2,3,4,5,6,7,8,99,0,99},{1,2,3,4,5,6,7,8,99,0}};
	int a[n][n];//定义距离矩阵
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			a[i][j]=c[i][j];
	for (i=0; i<n; i++)
		for(j=0; j<n; j++)
		{
			cout<<c[i][j]<<"  ";
			if(j==9) cout<<endl;
		};//输出c[][]
	for (k=0; k<n; k++)
		for(i=0; i<n; i++)
			for(j=0;  j<n; j++)
			{
				if( a[i][j]>a[i][k]+a[k][j] )
					a[i][j]=a[i][k]+a[k][j];
			};//查找
	for (i=0; i<n; i++)
		for(j=0; j<n; j++)
		{
			cout<<a[i][j]<<"  ";
			if(j==9) cout<<endl;
		};//输出a[][]
}