赞
踩
#include<bits/stdc++.h> #define MAXINT 0x3f3f3f3f #define Line cout<<"-----------------------------------------\n" using namespace std; typedef struct{ int n,m;//城市数,路径数 int **data;//邻接矩阵 string *cityname;//存城市名 }Seq; int y; void menu() { cout<<" **************************************\n\n"; cout<<" 实验:基于Dijsktra算法的最短路求解:\n\n"; cout<<" 1.邻接矩阵创建图\n"; cout<<" 2.求两个指定点之间的最短路径\n"; cout<<" 0.退出\n\n"; cout<<" **************************************\n\n"; } int LocateVex(Seq G,string c)///查找城市c在图中的位置 { for(int i=0;i<G.n;i++) if(c==G.cityname[i]) return i; return -1; } bool CreatGraph(Seq &G)///邻接矩阵建图 { int dis,s,e;string start,end1; cout<<"请输入城市个数:";cin>>G.n; cout<<"请输入城市间路径条数:";cin>>G.m; if(!G.n)///城市数为0的情况 return false; G.data=new int*[G.n]; for(int i=0;i<G.n;i++)G.data[i]=new int[G.n]; G.cityname=new string[G.n]; cout<<"请输入每个城市的名称:"; for(int i=0;i<G.n;i++) cin>>G.cityname[i]; for(int i=0;i<G.n;i++) for(int j=0;j<G.n;j++) if(i==j)G.data[i][j]=0; else G.data[i][j]=MAXINT; cout<<"请输入每条路径的起始点、终点和距离:\n"; for(int j=1;j<=G.m;j++){ cin>>start>>end1>>dis; s=LocateVex(G,start),e=LocateVex(G,end1); if(s==-1||e==-1){ cout<<"该条路径不符合标准,请重新输入!\n"; j--; continue; } if(dis<0||dis>MAXINT){ cout<<"该条路径的长度不符合标准,请重新输入!\n"; j--; continue; } if(dis<G.data[s][e])///重边情况 G.data[s][e]=dis; } return true; } void Dijkstra(Seq G)///Dijkstra算法 { string start,end1; cout<<"请输入待求最短路径的城市起点和终点:"; cin>>start>>end1; int s,e,t=0; s=LocateVex(G,start),e=LocateVex(G,end1); if(s==-1||e==-1){ cout<<"该输入不符合标准,请重新输入!\n"; return; } if(s==e){///自环情况 cout<<start<<"和"<<end1<<"之间最短路径长度为:0\n"; cout<<"该路径为:"<<start<<"\n"; return; } int dis[G.n]={},book[G.n]={},path[G.n]={};///三个数组作用分别为记录最短路径长度,标记作用,记录前驱点 for(int i=0;i<G.n;i++){ dis[i]=G.data[s][i]; if(dis[i]<MAXINT) path[i]=s; else path[i]=-1; } book[s]=1; for(int j=1;j<G.n;j++){ int MINdis=MAXINT,k=-1; for(int i=0;i<G.n;i++){ if(!book[i]&&dis[i]<MINdis){ MINdis=dis[i]; k=i; } } if(k==-1){ cout<<start<<"和"<<end1<<"之间不存在路径!\n"; return; } book[k]=1; if(k==e)break; for(int w=0;w<G.n;w++){ if(!book[w]&&dis[k]+G.data[k][w]<dis[w]){ dis[w]=dis[k]+G.data[k][w]; path[w]=k; } } } if(dis[e]<MAXINT) cout<<start<<"和"<<end1<<"之间最短路径长度为:"<<dis[e]<<endl; else{ cout<<start<<"和"<<end1<<"之间不存在路径!\n"; return; } /*输出路径*/ cout<<"该路径为:"; int node[G.n]={},q=1,y=1,i=e; while(y||q){ if(y&&i!=s){ node[q++]=i; i=path[i]; } else{ cout<<G.cityname[i]<<' '; i=node[--q]; y=0; } } cout<<"\n"; } /* void OUT(Seq G) { for(int i=0;i<G.n;i++){ for(int j=0;j<G.n;j++){ if(G.data[i][j]==MAXINT) cout<<"#"<<' '; else cout<<G.data[i][j]<<' '; } cout<<endl; } } */ int main() { menu(); Seq Graph; int choose=-1; while(choose){ cout<<"\n请输入指令:"; cin>>choose; if(!y&&choose!=1&&choose!=0){ cout<<endl;Line; cout<<"请先建图!\n"; Line;continue; } cout<<endl;Line; switch(choose){ case 0: cout<<"退出成功!\n";Line;break; case 1: system("cls");menu();Line; if(CreatGraph(Graph)) cout<<"创建图成功!\n"; else cout<<"创建图失败!\n"; Line;y=1; break; case 2: Dijkstra(Graph); Line; break; default:cout<<"指令不存在,请重新输入!\n"; Line; break; } } return 0; } /* 1 2 5 2 3 2 4 1 2 1 5 4 2 4 9 5 4 7 5 2 6 3 5 6 6 3 2 5 6 5 */
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。