main.cpp

实现Floyd算法的程序

#include <iostream.h>

void main()
{
	const int m = 3500;
	int matric[5][5] = {{0,10,m,30,100},
						{m,0,50,m,m},
						{m,m,0,20,10},
						{m,m,20,0,60},
						{m,m,m,m,0}};
	int patch[5][5];
	int a[5][5];
	
	int i,j,k,pre;
	
	for (i=0; i<5; i++)
	{
		for (j=0; j<5; j++)
		{
			a[i][j] = matric[i][j];
			patch[i][j] = j;
		}
	}

	for (k=0; k<5; k++)
	{
		for (i=0; i<5; i++)
			for (j=0; j<5; j++)
			{
				if(a[i][j] > a[i][k] + a[k][j])
				{
					a[i][j] = a[i][k] + a[k][j];
					patch[i][j] = patch[i][k];
				}
			}
	}

	for (i=0; i<5; i++)
		for (j=0; j<5; j++)
		{
			if(a[i][j] == m)
			{               
				cout<<"there is no patch form "<<i<<" to "<<j<<endl;
			}
			else
			{
				cout<<"the distance from "<<i<<" to "<<j<<" is "<<a[i][j];
				cout<<"    the patch is :"<<i;
			
				pre = i;
				do
				{
					pre = patch[pre][j];
					cout<<"-->"<<pre;	
				}while (pre != j);
				cout<<endl;
			}
		}

}