floyd1.cpp

可进行假设的社区网图中医院应该所在的中心点的选择

//Floyd1.cpp 医院选址
#include <iostream>
//#include <iomanip.h>
#include <string>                   //引入标准库中的头文件
#include "graph.cpp"                //引用graph.cpp文件
using namespace std;                
template <class T>
void MGraph<T>::Floyd1()    //类成员函数
{int dist[N][N];
 int path[N][N];
 int i,j,k;
 for (i=0; i<vertexNum; i++)        
  for (j=0; j<vertexNum; j++)
  { dist[i][j]=arc[i][j];
    if (dist[i][j]!=999) path[i][j]=i; else path[i][j]=-1;  
  }
  for (i=0; i<vertexNum; i++) path[i][i]=-1;//自己到自己
 for (k=0; k<vertexNum; k++)         
   for (i=0; i<vertexNum; i++)       
     for (j=0; j<vertexNum; j++)
        if (dist[i][k]+dist[k][j]<dist[i][j])
          { dist[i][j]=dist[i][k]+dist[k][j];
            path[i][j]=path[k][j];
		  }  
cout<<"dist[][]:"<<endl;
for (i=0; i<vertexNum; i++)       
{ for (j=0; j<vertexNum; j++)
    if(dist[i][j]<999)cout<<dist[i][j]<<"\t";
	else cout<<"\t";
  cout<<endl;
}
//医院选址：每列中求最大，然后对他们求最小。
//用一个辅助的结构数组来完成
int loc[MaxSize];
for(j=0;j<vertexNum;j++)// 求出每列中的最大值及其所在的行号
{int M=0;int l=0;
 for(i=0;i<vertexNum;i++) 
	 if (dist[i][j]>M)
		 M=dist[i][j]; 
 loc[j]=M;
}//已求得每列中的最大值
cout<<"输出每个顶点的偏心度"<<endl;
for (j=0;j<vertexNum;j++) cout<<vertex[j]<<" "<<loc[j]<<endl;
//现在求每列中最大者的最小者
int M=999;int l=0;
for (j=0;j<vertexNum;j++)
   if (loc[j]<M) {M=loc[j];l=j;}

//输出中心点
cout<<"输出中心点"<<endl;
cout<<"中心点："<<vertex[l]<<" 结点下标号:"<<l<<endl;
 

cout<<"path[][]:"<<endl;
for (i=0; i<vertexNum; i++)       
{ for (j=0; j<vertexNum; j++)
    if(dist[i][j]<999)cout<<path[i][j]<<"\t";	else cout<<"\t";
  cout<<endl;
}
for (i=0; i<vertexNum; i++)       
{ cout<<"row="<<i<<":";
  for (j=0; j<vertexNum; j++){
	  if(dist[i][j]<999)
	  {cout<<j<<": ";
	   k=path[i][j];
	   while(k!=-1)
	   {cout<<k<<"  ";
	    k=path[i][k];
	   }
	   cout<<"；";
	  }
  	  else cout<<"     ";
  }
  cout<<endl;
}
}