floyed.cpp

floyd算法 数据结构 求最短路径

// floyed.cpp : Defines the entry point for the console application.
//
/*五、寻径问题： （难度系数：1.3)
给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连接，
边上的权Wij 表示这条道路的长度。现在要从这n个村庄选择一个村庄建一所医院，
问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的距离最短？
试设计一个算法来解决该问题。
*/

typedef char VerT;
typedef char Datatype;

#include "conio.h"  // 使用getch()
#include "AdjMWGraph.h"
#include "GraphLib.h"
#include "iomanip.h"  // 使用setw(3)

#define m 10
int distance[m][m];//用来存储边与边的权值
int path[m][m];//用来存储当前得到最短路径
int WSM[m][m];

void floyed(AdjMWGraph &g)//佛洛依德算法
{
	int i,j,k,minfloy;
	int n=g.NumOfVertices();
	for (i=0;i<n;i++)//初始化
		for (j=0;j<n;j++)
		{
			path[i][j]=-1;//初始化path为-1
			distance[i][j]=g.GetWeight(i,j);
		}
	for (k=0;k<n;k++)//n次递推
	{   minfloy=MaxWeight;
		for (i=0;i<n;i++)
			for (j=0;j<n;j++)
			{
				if (distance[i][j]>distance[i][k]+distance[k][j])
				{   //得到新的最短路径长度数值
					distance[i][j]=distance[i][k]+distance[k][j];
					//得到该最短路径经过的结点序号
					path[i][j]=k;
				}
			}
	}
	//当不存在路径时算法结束（此语句对非连通图是必需的）
	if(minfloy==MaxWeight) return;
}
 
void Warshall(AdjMWGraph &g)
{
  int i,j,k;
 	int n=g.NumOfVertices();
	for (i=0;i<n;i++)//初始化
		for (j=0;j<n;j++)
		{
			if(i==j)
			    	WSM[i][j]=1;
			else if(g.GetWeight(i,j)<MaxWeight)
					WSM[i][j]=1;
	    	else 
			    WSM[i][j]=0;
		}

	  for (i=0;i<n;i++)//n次递推
		for (j=0;j<n;j++)
		 if(i!=j)
		 {
		    k=0;
			while(WSM[i][j]==0 && k<n)
			{
			   WSM[i][j]=WSM[i][k]*WSM[k][j];
			   k++;
			}
		 }
}

void printpath(AdjMWGraph &g,int i,int j)//打印最短路径
{ int k;
  k=path[i][j];
  if (k!=-1)
    { printpath(g,i,k);
      cout<<"-->"<<g.GetValue(k);
      printpath(g,k,j);
    }
}



void main(void)
{ 
	AdjMWGraph g;  	
//	char a[]={'A','B','C','D'};
//	RowColWeight rcw[]={{0,1,10},{1,0,15},{1,2,6},{2,0,3},//建立一个有向连通图（用村庄A，B，C，D表示），
//		      			{2,3,4},{3,1,8},{3,2,2}};        // 并设定好对应边上的权值即村庄之间的距离
//	int n=4,e=7;
//	int i,j,maxcol;
	char *a=new char[];
	char x,y;
	int i,j,k,n,e,r=0;
	int maxcol;
    cout<<"村庄的个数：";
	cin>>n;
	RowColWeight *rcw=new RowColWeight[n*n];
	cout<<"你所输入的村庄是：";
	for(k=0;k<n;k++)
	{	a[k]=k+65;
		cout<<a[k]<<"\t";
	}
	cout<<endl<<"请输入边数：";
	cin>>e;
	cout<<"请输入任意两个村庄的距离（例如：A B 20）："<<endl; 
	for(k=0;k<e;k++)//按用户的需要输入各个村庄之间的距离
	{   
		cin>>x;
		i=int(x-65);
		cin>>y;
	    j=int(y-65);
		rcw[k].row=i;
		rcw[k].col=j;
		cin>>rcw[k].weight;
	}
	CreatGraph(g,a,n,rcw,e);
	floyed(g);

 	cout<<"\n你所输入的矩阵图为：\n"<<endl;
	for(k=0;k<n;k++)
	{	a[k]=k+65;
		cout<<"  "<<setw(3)<<a[k];
	}
	for (i=0;i<n;i++)
	{
	  cout<<endl;
	  for (int j=0;j<n;j++) 
		  cout<<"  "<<setw(3)<<g.GetWeight(i,j);
    }
	cout<<endl;
  

	
	cout<<endl<<"\n各村庄之间的最短路径长度的矩阵序列是 :"<<endl;
	for(k=0;k<n;k++)
	{	a[k]=k+65;
		cout<<"  "<<setw(3)<<a[k];
	}
   for (i=0;i<n;i++)//生成村庄的最短路径长度的矩阵
   { 
	  cout<<endl;
	  for (j=0;j<n;j++) 
		  cout<<"  "<<setw(3)<<distance[i][j];
    }
	cout<<endl;

    cout<<"\n\n各列最大值：";
	for(i=0;i<n;i++)//输出各个村庄最短路径的长度的最大值
	{  int mincol=0;
	     maxcol=distance[0][0];
	   for(j=0;j<n;j++)
		   if(distance[j][i]>maxcol)
		       maxcol=distance[j][i];
			   cout<<maxcol<<setw(5);
			   if(mincol<maxcol)
			   {  mincol=maxcol;
			           r=j;
			   }
	}
	cout<<endl;	
	if(maxcol==MaxWeight) return;
	cout<<"\n所以医院应建在村庄"<<(char)(65+r)<<endl;
	
}