交通图.cpp

最短路课程设计

#include <iostream.h>
#include <fstream.h>
#include <limits.h>
#include<cstring>
#include<stdlib.h>
#include   <iomanip.h>   
#define N 30//最大顶点数；
typedef struct{
	char name[10];
	int info;//可以是其他东西，这里指它在图中的序号
} VertexType;
struct MGraph
{
	VertexType vex[N];
    int vexnum;//顶点数；
    int p[N][N];//邻接矩阵；

};

MGraph  g;
typedef int pathmatrix[N][N][N];
typedef int distanctrix[N][N];

char *GetVex(MGraph g,int i)
{
	char *city=new char;
	strcpy(city,g.vex[i].name);
	return city;
}
void ShortestPath_Floyd(MGraph g ,pathmatrix  q ,distanctrix  d)//用FLOYD算法，求每对顶点间的最短距离；
{
	int u,v,w ,i;
	for(v=0;v<g.vexnum;v++)
		for(w=0;w<g.vexnum;w++)
		{
			d[v][w]=g.p[v][w];
			for (u=0;u<g.vexnum;u++)
			q[v][w][u]=false;
			if(d[v][w]<INT_MAX)
				q[v][w][v]=q[v][w][w]=true;//q==true，则在路径上
		}
			for(u=0;u<g.vexnum;u++)
		      for(v=0;v<g.vexnum;v++)
		        for(w=0;w<g.vexnum;w++)
				
					if (d[v][u]<INT_MAX && d[u][w]<INT_MAX && (d[v][u]+d[u][w])<d[v][w])
					{
						d[v][w]=d[v][u]+d[u][w];
						for(i=0;i<g.vexnum;i++)
							q[v][w][i]=q[v][u][i]||q[u][w][i];
					}

}
void path(MGraph g,pathmatrix q,int i,int j)//起点i，到终点j，经过的地点（路径）；
{
	int k ;
	int m=i;//起点
	while (m!=j)
	{
		g.p[m][m]=INT_MAX;
		for (k=0;k<g.vexnum;k++)
		{
			if (g.p[m][k]<INT_MAX && q[m][j][k])
			{
				
			    
				cout<<GetVex(g,m);;
				g.p[m][k]=g.p[k][m]=INT_MAX;
				m=k;cout<<"→";
				break;
			}
			
		}
	}
	cout<<GetVex(g,j)<<endl;

}


void Initialization()
{
	cout<<"************************************"<<endl;
	cout<<"*求最短路-m   " <<'\t'<<"退出-q\t*   "<<endl;
	cout<<"************************************"<<endl;
    cout<<endl<<"输入你想要的操作:";

}
void main()
{
	int i,j,r=1;
	MGraph g;
	pathmatrix  q;
	distanctrix  d;
	fstream file;
    file.open ("mape.txt",ios::in);
    file>>g.vexnum;	
    for(i=0;i<g.vexnum;i++)
    {
        file >> g.vex[i].info;
		file >> g.vex[i].name;
	}
	for(i=0;i<g.vexnum;i++)
	{
		for(j=0;j<g.vexnum;j++)
			if (i==j)    g.p[i][j]=0;
			else g.p[i][j]=INT_MAX;
	}
	while (!file.eof())
	{
		file>>i>>j;
        file>>g.p[i][j];
		g.p[j][i]=g.p[i][j]; 
	}
     file.close();	
	 cout<<"交通图邻接矩阵如下："<<endl;
	 for(i=0;i<g.vexnum ;i++)
	 {
		for(j=0;j<g.vexnum;j++)
		{
			if(g.p[i][j]==INT_MAX)  cout<<setw(4)<<"∞";
			else 
			cout<<setw(4) <<g.p[i][j]; 
		}
		cout<<endl;
	 }
	cout<<endl;
	Initialization();
	char c;
    do
	{	
	  cin >> c;
	  switch(c)
	  {
	  case 'm':
	  case 'M':int start,end;
		       ShortestPath_Floyd(g ,q ,d); 
		        cout<<"请输入起点代号:";
				cin>>start;
		        cout<<"\n请输入终点代号";
			    cin >>end;
				                    
	            cout<<endl<<"请验证路经："<<endl; 
		        if(d[start][end]<INT_MAX)
				{   
				cout<<"起点与终点最短距离为"<<" ";
				cout<<d[start][end]<<endl;
				cout<<"路径为"<<endl;
			    path(g,q,start,end);  
				cout<<endl;
				}
	  case 'q':
	  case 'Q':  exit(-1);
		         break;
	  default:  "\nPlease input again:";
		        cin>>c;
	  }
	  	Initialization();
	}while(c!='q'||c!='Q');
}