1611.cpp

最短路径实现全国铁路查询

#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
 struct node
 {int time;int counter;}; 
int p[100][100];int D[100][100];	
int i,j,k,V,W,s;
 struct MGraph
{
char * vexs[100]; node arcs[100][100];//存储各个顶点之间和边的信息
int vexnum,arcnum;//顶点数目和边的数目
} ;
void InitGraph(MGraph & dx)
{//对图的初始化
    dx.arcnum=dx.vexnum=0;//初始化顶点数和边数都为0
	for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
		{dx.arcs[i][j].counter=0;//在初始情况下各个顶点之间均没有边相连
	    dx.arcs[i][j].time=99999;}
}
int FindVex(MGraph dx,char *vex){//查找顶点vex是否存在
	for(int i=1;i<=dx.vexnum;i++){
		if(strcmp(dx.vexs[i],vex)==0)
			return i;//顶点存在，返回i
	}
	return 0;//顶点不存在，返回0
}
int FindArc(MGraph dx,char *v1,char *v2,int m)
{//查找边<v1,v2>是否存在
	int x,y;
	x=FindVex(dx,v1);
	y=FindVex(dx,v2);
	if(x==0 || y==0) return 0;//某个顶点不存在，边肯定不存在，返回0
	if(dx.arcs[x][y].counter==1)
		return 1;//边存在，返回1
	return 1;
}
void InsertVex(MGraph &dx,char *vex)
{//插入一个顶点vex
	if(FindVex(dx,vex)==0)//顶点不存在
	{
		dx.vexnum++;//开辟一个空间
		dx.vexs[dx.vexnum]=new char[strlen(vex)];
		strcpy(dx.vexs[dx.vexnum],vex);//新顶点加入
	}	

}
void InsertArc(MGraph &dx,char *v1,char *v2,int m)
{//插入一条边<v1,v2>
	int x,y;
	x=FindVex(dx,v1);
	y=FindVex(dx,v2);
	if(x && y)
	{
	dx.arcs[x][y].counter=1;dx.arcnum++;
dx.arcs[x][y].time=m;dx.arcs[y][x].time=m;
dx.arcs[x][x].time=0;dx.arcs[y][y].time=0;
	}	
}

void print(MGraph &dx)
{
	cout<<"*************************************************************************"<<endl;
	cout<<"*********************************列车表**********************************"<<endl;
	cout<<"*************************************************************************"<<endl;
	for(int i=1 ;i<=dx.vexnum;i++)
	{
		cout<<left;
	cout<<setw(14)<<dx.vexs[i];
	if(i%5==0)
	{	cout<<endl;}
	 }
cout<<endl;
}	

void Floyd(MGraph &dx)
{
	for(i=1;i<=dx.vexnum;i++)
	{//对图初始化
		for(j=1;j<=dx.vexnum;j++)
		{	if(dx.arcs[i][j].time!=99999)
			p[i][j]=j;
			else
             p[i][j]=0;//顶点i和顶点j之间的路径初始时就是ij。
			D[i][j]=dx.arcs[i][j].time;//路径值为边（i，j）的权值
		}
	} 

for(k=1;k<=dx.vexnum;k++)
	 {//对于每一个顶点都要试探
		for(i=1;i<=dx.vexnum;i++)
		{
			for(j=1;j<=dx.vexnum;j++)//在顶点i和顶点j之间的路径上试探k
			{
				if(i==j)continue;//对角线上的元素（即顶点自身之间）不予考虑
					if(D[i][k]+D[k][j]<D[i][j])
					{//发现更短的路径
						D[i][j]=D[i][k]+D[k][j];//新的i、j间的路径由两部分组成
						//p[i][k]+p[k][j]
						p[i][j]=p[i][k];
					}
			}
		}
	 }
}
void main()
{
  MGraph dx;
	 InitGraph(dx);//图的初始化
    InsertVex(dx,"1.乌鲁木齐");//插入顶点
	InsertVex(dx,"2.西宁");InsertVex(dx,"3.兰州");InsertVex(dx,"4.呼和浩特");
	InsertVex(dx,"5.西安");InsertVex(dx,"6.成都");InsertVex(dx,"7.昆明");
	InsertVex(dx,"8.贵阳");InsertVex(dx,"9.柳州"); InsertVex(dx,"10.南宁");  
	InsertVex(dx,"11.株洲");InsertVex(dx,"12.广州"); InsertVex(dx,"13.深圳");  
	InsertVex(dx,"14.武汉");InsertVex(dx,"15.郑州");InsertVex(dx,"16.北京");
	InsertVex(dx,"17.天津");InsertVex(dx,"18.徐州");InsertVex(dx,"19.上海");
	InsertVex(dx,"20.南京");InsertVex(dx,"21.福州");InsertVex(dx,"22.大连");
    InsertVex(dx,"23.沈阳");InsertVex(dx,"24.长春");InsertVex(dx,"25.哈尔滨");
	InsertArc(dx,"1.乌鲁木齐","3.兰州",1892);//插入边
	InsertArc(dx,"2.西宁","3.兰州",216);InsertArc(dx,"3.兰州","4.呼和浩特",1145);
	InsertArc(dx,"3.兰州","5.西安",676);InsertArc(dx,"5.西安","6.成都",842);    
 	InsertArc(dx,"6.成都","7.昆明",1100);InsertArc(dx,"6.成都","8.贵阳",967);
    InsertArc(dx,"7.昆明","8.贵阳",639);InsertArc(dx,"8.贵阳","9.柳州",607);
	InsertArc(dx,"9.柳州","10.南宁",255);InsertArc(dx,"9.柳州","11.株洲",672);
	InsertArc(dx,"8.贵阳","11.株洲",902);InsertArc(dx,"11.株洲","12.广州",675);
	InsertArc(dx,"12.广州","13.深圳",140);InsertArc(dx,"11.株洲","14.武汉",409);    
 	InsertArc(dx,"14.武汉","15.郑州",534);InsertArc(dx,"15.郑州","16.北京",695);
    InsertArc(dx,"16.北京","17.天津",137);InsertArc(dx,"5.西安","15.郑州",511);
	InsertArc(dx,"15.郑州","18.徐州",349);InsertArc(dx,"17.天津","18.徐州",674);
	InsertArc(dx,"18.徐州","19.上海",651);InsertArc(dx,"19.上海","20.南京",825);
	InsertArc(dx,"11.株洲","20.南京",367);InsertArc(dx,"20.南京","21.福州",842);    
 	InsertArc(dx,"17.天津","23.沈阳",704); InsertArc(dx,"23.沈阳","22.大连",397);
    InsertArc(dx,"23.沈阳","24.长春",305);	InsertArc(dx,"24.长春","25.哈尔滨",242);
	print(dx);
int  count=1;
if(count==1)
{cout<<setw(42)<<"****************************欢迎使用交通系统***********************"<<endl;}
cout<<"\n\n\n";
while(count!=0)
{
 
	Floyd(dx);
    cout<<"按照城市前面的编号查询"<<endl;
	cout<<"\n";
	cout<<"输入起点：";cin>>V;cout<<endl;
	cout<<"输入终点：";cin>>W;cout<<endl;
   
    k=p[V][W];

  if(k==0){cout<<"V,W之间无路径:"<<endl;}
  else
  {
	cout<<"路径是:"<<V<<"->"; 
while(k!=W)
{
	cout<<k<<"->";
     k=p[k][W];
}
cout<<W<<endl;
cout<<"路径长度："<<D[V][W]<<endl;}
  L:cout<<"是否继续，1 继续，0 退出"<<endl;
cout<<"请输入选择方式：";
cin>>count;
if(count==0){cout<<setw(42)<<"祝您旅途愉快："<<endl;
return ;
}
if(count==1)
cout<<setw(46)<<"欢迎再次使用交通系统:"<<endl;

else
{ 
cout<<"输入错误！！"<<endl;
goto L;
}


}
}