floyd.c

求多源最短路径的一个算法,编码风格清晰明了

#include<iostream>
#include<iomanip>
using namespace std;
#define N 11

int A[N][N];
int count = 0;

void showPass()
{
	cout<<"A"<<count<<":";
	for(int i=0; i<N; i++)
	{
		cout<<endl;
		for(int j=0; j<N; j++)
			cout<<setw(3)<<A[i][j];	
	}
	cout<<endl;
	count++;
}

void allPaths(int Cost[N][N])
{
	int i,j,k;
	for(i=0; i<N; i++)
		for(j=0; j<N; j++)
			A[i][j] = Cost[i][j];	
		
		for(k=1; k<N; k++)
		{
			showPass();	
			for(i=1; i<N; i++)	
				for(j=1; j<N; j++)							
					if(A[i][j] > A[i][k] + A[k][j])			
						A[i][j] = A[i][k] + A[k][j];					
		}	
		showPass();
}

int main()
{
	int C[N][N] = {	{0,1,2,3,4,5,6,7,8,9,10},
						{1,0, 99, 8, 7, 6, 5, 4, 3, 2, 1},
						{2,99, 0, 99, 8, 7, 6, 5, 4, 3, 2},
						{3,8, 99, 0, 99, 8, 7, 6, 5, 4, 3},
						{4,7, 8, 99, 0, 99, 8, 7, 6, 5, 4},
						{5,6, 7, 8, 99, 0, 99, 8, 7, 6, 5},
						{6,5, 6, 7, 8, 99, 0, 99, 8, 7, 6},
						{7,4, 5, 6, 7, 8, 99, 0, 99, 8, 7},
						{8,3, 4, 5, 6, 7, 8, 99, 0, 99, 8},
						{9,2, 3, 4, 5, 6, 7, 8, 99, 0, 99},
						{10,1, 2, 3, 4, 5, 6, 7, 8, 99, 0} 
										
		};
	
	allPaths(C);
	return 0;
}