jiaotong.rar_交通咨询系统_城市 最短路径_所有路径_最短路径 查找_路径 咨询 系统

#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); }