graphtest.cpp

给定n个小区之间的交通图。若小区i与小区j之间有路可通

#include <iostream.h>
#include <stdlib.h>

typedef char VerT;
typedef char DataType;	
const int MaxVertices = 100;
const int MaxWeight = 9999;
	
#include "AdjMWGraph.h"

#include "CreatAdjMWGraph.h"

void Floyed(AdjMWGraph &g,int best[][4],int n)
   //利用Floyed算法求g表示的图中每对顶点之间的最短长度，
   //对应保存于二维数组best中。
{
	 int i,j,k;
	 // 给二维数组best赋初值，它等于图的邻接矩阵Edge
	 for(i=0;i<n;i++)
	   for(j=0;j<n;j++)
		   best[i][j]=g.Edge[i][j];
	  
	   //依次以每个顶点作为中间点，逐步优化数组best.
	   for(k=0;k<n;k++)
		   for(i=0;i<n;i++)
			   for(j=0;j<n;j++)
			   {   if(i==k||j==k||i==j) continue;
			       if(best[i][k]+best[k][j]<best[i][j])
					   best[i][j]=best[i][k]+best[k][j];
			   }
}

void main(void)
{
	AdjMWGraph g;
	char a[] = {'0','1','2','3'};
	RowColWeight rcw[] = {{0,1,1},{1,0,1},{0,2,13},{2,0,13},{0,3,4},
						{3,0,4},{1,3,2},{3,1,2},{2,3,8},{3,2,8},
						{2,1,9},{1,2,9}};
	int n =4, e = 12;
	int best[4][4];
    int best2[4];
	
	CreatGraph(g, a, n, rcw, e);				//创建图8-10
	Floyed( g, best, n);           //调用Floyed算法
    
	cout<<"建立最短路径矩阵："<<endl;
	for(int i=0;i<n;i++)
	 {for(int j=0;j<n;j++)
		  cout<< best[i][j]<<"   " ;
          cout<<endl;
	 }
    //找出从每个顶点到其他各顶点的最短路径中的最长路径 
	for(i=0;i<n;i++)
	{  best2[i]=best[i][0];
		for(int j=0;j<n;j++) 
			if(best[i][j]>best2[i])
				best2[i]=best[i][j];
		cout<<"从第"<<i<<"个到其他各顶点的最短路径中最长路径为："<<best2[i]<<endl;
		cout<<endl;
	}
    int min=best2[0];
	int dian=0;
    for(i=1;i<n;i++)
	{  
		if(best2[i]<min){ min=best2[i];dian=i;}
	}
	cout<< "此四条最长路径中最短的一条为： "<<min<<"  起点为: "<<dian<<endl<<endl;   
	cout<<"医院应建在第"<<dian<<"个小区."<<endl;
  }