c7_floyd.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
Floyd
BY：wangyucao
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<vector>
#include<queue>
#define MAX 125
#define Maxint 1000000
using namespace std;

int map[MAX][MAX],dis[MAX];
int n,m,sum=0;
bool p[MAX][MAX][MAX];

void init()
{
	int i,j,l;
	memset(p,false,sizeof(p));
	cin>>n;
	for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
	  map[i][j]=Maxint;	
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			cin>>l;
			if(l>0)
			{
				map[i][j]=l;
			//	map[j][i]=l;       //无向图时可去掉前面注释
				p[i][j][i]=true;
				p[i][j][j]=true;
			}
		}
}

void Floyd()
{
	int u,v,w,i;
	for(u=0;u<n;u++)
		for(v=0;v<n;v++)
			for(w=0;w<n;w++)
			{
				if(map[v][u]+map[u][w]<map[v][w])
				{
					map[v][w]=map[v][u]+map[u][w];
					for(i=0;i<n;i++)
						p[v][w][i]=p[v][u][i]||p[u][w][i];
				}
			}

}
int main()
{
	init();
	Floyd();
	cout<<endl;
	for(int i=0;i<n;i++)
	{
       for(int j=0;j<n;j++)       
	   if(i!=j) cout<<map[i][j]<<' ';
	   else cout<<"0 ";
	   cout<<endl;
}
	   
	system("PAUSE");
	return 0;
}