交通咨询系统.cpp

这是一个交通咨询系统

#include<iostream.h>
const int MaxVerNum=20;   //交通图的顶点数的最大值
const int MAXVALUE=100000;   //两点间通路权值的最大值
typedef struct{
	char vexs[MaxVerNum];
	int edges[MaxVerNum][MaxVerNum];
	int Vnum,Enum;
}MGraph;  // 相应邻接矩阵
////////////////////////////////////////
          // 相应邻接矩阵的建立 
void CreateMGraph(MGraph * G)
{
	// 建立相应邻接矩阵
	int i,j,s,k;
	cout<<"请输入交通图的顶点数和边数（输入格式为:顶点数，边数）:"<<" ";
	cin>>G->Vnum>>G->Enum;
	while(G->Vnum>MaxVerNum||G->Enum>MaxVerNum*(MaxVerNum-1))
	{
		cout<<"输入值过大，请重新输入:"<<endl;
		cin>>G->Vnum>>G->Enum;
	}
	cout<<"请输入顶点信息（输入格式为:顶点号）:"<<endl;
	for(i=0;i<G->Vnum;i++)
		cin>>G->vexs[i];
	for(i=0;i<G->Vnum;i++)
		for(j=0;j<G->Vnum;j++)
			G->edges[i][j]=MAXVALUE;
	cout<<"两顶点间边边的输入格式为:i　j（i->j）"<<endl;
	for(k=0;k<G->Enum;k++)
	{
		cout<<"请输入一条边:"<<" ";
		cin>>i>>j;
		while(i<=0||j<=0||i>G->Vnum||j>G->Vnum)
		{
			cout<<"输入有误，请重新输入该边:"<<endl;
			cin>>i>>j;
		}
		cout<<"请输入对应的费用:"<<" ";
		cin>>s;
		while(s<=0)
		{
			cout<<"输入有误(不应为负值)，请重新输入:"<<endl;
			cin>>s;
		}
		G->edges[i-1][j-1]=s;
	}
}
/////////////////////////////////////////////////////////////////////
                  //   单源查询
void Shortest_one_head(MGraph * G,int v0,int P[],int D[])
{
	// 可查询以v0为起点，到其他各顶点费用（或时间）最小的路径
	int i,v,w;
	int min;
	int MAXINT=MAXVALUE;
	int final[MaxVerNum+1];
	for(v=1;v<=G->Vnum;v++)
	{	
		final[v]=0;
		D[v]=G->edges[v0-1][v-1];  
		if(D[v]<MAXINT&&v!=v0)
			P[v]=v0;
		if(D[v]==MAXINT)
			P[v]=-2;
	}
	P[v0]=-1;    //v0无前驱接点，将其值负为-1
	D[v0]=0;
	final[v0]=1;
	for(i=1;i<G->Vnum;i++)
	{
		min=MAXINT;
		for(w=1;w<=G->Vnum;w++)
			if(!final[w]&&D[w]<min)
			{
				v=w;
				min=D[w];
			}
		final[v]=1;
		for(w=1;w<=G->Vnum;w++)
			if(!final[w]&&(min+G->edges[v-1][w-1]<D[w]))
			{
				D[w]=min+G->edges[v-1][w-1];
				P[w]=v;
			}
	}
}
////////////////////////////////////////////////////////////
                    //  显示最短路径和费用
void show_lujing(int d,int P[],MGraph * G)
//显示当前源点到d顶点的路径
{
	int pre;
	if(P[d]==-2)
		cout<<d<<" 不可到达.";
	else if(P[d]==-1)
			cout<<d<<": 最短路径:"<<d<<"<--"<<d;
		else
		{
			pre=P[d];
			cout<<d<<": 最短路径:"<<d;
			while(pre>0)
			{
				cout<<"<--"<<pre;
				pre=P[pre];
			}
		}
}
void show_dist(int d,int D[])//显示dist[d]
{
	if(D[d]!=MAXVALUE)
	   cout<<"  费用: "<<D[d];
	cout<<endl;
}
////////////////////////////////////////////////////////////
                 /// 单源&&两点查询
void one_head(MGraph * G,int P[],int D[])
{
	//单源最短路径查询
	int v0;
	cout<<"请输入起始位置:"<<" ";
	cin>>v0;
	Shortest_one_head(G,v0,P,D);
	cout<<v0<<" 到其他各点的最短路径和费用:"<<endl;
	for(int i=1;i<=G->Vnum;i++)
	{
		if(i!=v0)
		{
		show_lujing(i,P,G);
		show_dist(i,D);
		}
	}
}
void two_points(MGraph * G,int P[],int D[])
{
	//  任意两点间的查询
	int i,j;
	cout<<"请输入要查询的起始点和终点的序号:"<<" ";
	cin>>i>>j;
	while(i<1||j<1||i>G->Vnum||j>G->Vnum)
	{
		cout<<"输入有误，请重新输入:"<<" ";
		cin>>i>>j;
	}
	Shortest_one_head(G,i,P,D);
	cout<<"点"<<i<<"到点"<<j<<"的最短路径和费用:"<<endl;
	show_lujing(j,P,G);
	show_dist(j,D);
}
///////////////////////////////////////////////////////////
               //  连接函数
void user_choice(MGraph * G,int P[],int D[])
{
	int i=1;
	while(i>=1&&i<=3)
	{
		cout<<"1. 单源查询"<<'\t'<<"2. 两点查询"<<'\t'<<"3. 重置交通图"<<'\t'<<"0. 退出"<<endl;
	    cout<<"   请选择：";
		cin>>i;
		while(i<0||i>3)
		{
		cout<<"输入有误，请重新输入:"<<" ";
		cin>>i;
		}
		switch(i)
		{
		case 1:one_head(G,P,D);break;
		case 2:two_points(G,P,D);break;
		case 3:CreateMGraph(G);break;
		default:break;
		}		
	}
}
void main()
{
	
	MGraph A;
	MGraph * G=& A;
	int dist[MaxVerNum+1];	 //最短路径长度数组	
    int path[MaxVerNum+1];	 //最短路径数组
	CreateMGraph(G);
	user_choice(G,path,dist);
}