数据结构课设之校园导航系统（迪杰斯特拉算法）

#include<iostream> #include <stdlib.h> #include <conio.h> #include <string.h> using namespace std; const int INF=99999;//无穷 int way[100][100];//两景点之间的路径 string site[15];//景点名称 string passSite[15];//路过的景点 int dis[18]={0,10,20,15,25,25,10,15,25,8,10,12,12,5,18,10,16,23};//各单条路径的长度 int Dist[2200]; //int Dist[100][100];//两景点之间的路径 int book[100]; int pre[2200]; int m=17,n=14,u,v; int putIn()//为各地点填入具体信息 { memset(pre , -1 , sizeof(pre)); memset(way , INF , sizeof(way)); site[1] = "南门"; site[2] = "齐贤广场"; site[3] = "四环广场"; site[4] = "书香园"; site[5] = "教工三村"; site[6] = "西北校区-体育场"; site[7] = "学苑餐厅"; site[8] = "东南校区-体育场"; site[9] = "南苑餐厅"; site[10] = "领创空间"; site[11] = "北大门"; site[12] = "体育馆"; site[13] = "图书馆"; site[14] = "东门"; //初始化权值 for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(i == j) { way[i][j] = 0; } else { way[i][j] = INF; } } } way[1][2] = way[2][1] = dis[1];//南门__齐贤广场 way[1][3] = way[3][1] = dis[2];//南门__四环广场 way[2][4] = way[4][2] = dis[3];//齐贤广场__书香园 way[2][5] = way[5][2] = dis[4];//齐贤广场__教工三村 way[3][6] = way[6][3] = dis[5];//四环广场__西北校区-体育场 way[3][7] = way[7][3] = dis[6];//四环广场__学苑餐厅 way[4][8] = way[8][4] = dis[7];//书香园__东南校区-体育场 way[4][9] = way[9][4] = dis[8];//书香园__南苑餐厅 way[5][6] = way[6][5] = dis[9];//教工三村__西北校区-体育场 way[6][10] = way[10][6] = dis[10];//西北校区-体育场__领创空间 way[7][10] = way[10][7] = dis[11];//学苑餐厅__领创空间 way[8][9] = way[9][8] = dis[12];//东南校区-体育场__南苑餐厅 way[8][12] = way[12][8] = dis[13];//东南校区-体育场__体育馆 way[9][14] = way[14][9] = dis[14];//南苑餐厅__东门 way[10][11] = way[11][10] = dis[15];//领创空间__北大门 way[12][13] = way[13][12] = dis[16];//体育馆__图书馆 way[12][14] = way[13][12] = dis[17];//体育馆__东门 } //总体思路:先找与自己选中的点a最近的点p，再求出这个点p到其他有路径点的路径距离存入点a到点p的虚拟直接距离的数组中，在下一次循环中判断点a到各个点最近的点f，以此类推。 int distence_Calculate(int s)//用地杰斯特拉计算景点之间的路径 { n=14; for(int i=1;i<=n;i++) { Dist[i] = way[s][i]; book[i] = 0; pre[i] = -1; } book[s] = 1; int min=INF,u; for(int i=1;i<=n;i++) //找到离i号顶点最近的顶点 { min=INF; for(int j=1;j<=n;j++) { if(!book[j]&&Dist[j]<min)//最近的判断标志 { min=Dist[j];//找出最小邻接点 u=j; } } book[u]=1;//u顶点离i号顶点最近，将u顶点加入到book集合中 for(int v=1;v<=n;v++) { if(!book[v]&&Dist[v]>Dist[u]+way[u][v]) { Dist[v]=Dist[u]+way[u][v];//更新距离 pre[v] = u;//把这个中间点存入pre数组中 （在更新最短路的时候记录是从哪个点更新过来的)， } } } } void print(int v) { if(pre[v] == -1)//从终点沿着路径走回去，就可以得到最短的路径了 { cout<< site[v]; return; } print(pre[v]); cout <<"--->"<<site[v]; } void showsig()//显示地图中主要地点 { system("cls"); puts("\n\n\n\n\n"); printf("\t\t\t\t ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ \n"); printf("\t\t\t\t 欢迎进入 校园导航 \n"); printf("\t\t\t\t ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ \n"); puts("\n\n\n\t\t\t\t\t-------------------------------"); for(int i = 1 ; i <= 14 ; i++) { cout<<"\t\t\t\t\t~~~~~~~~~~~"<<i<<"."<<site[i]<<"~~~~~~~~~~~~"<<endl; } puts("\t\t\t\t\t-------------------------------"); } void gps()//定位并导航 { while(true){ int a,b; cout<<"您现在所处的位置："; cin>>a; if(a<=n&&a>=0){ if(a==0){ return; } cout<<"您想要到达的位置（输入0返回上一个界面）："; cin>>b; if(b<=n&&b>=0){ if(b==0) { return; } distence_Calculate(a); //cout<<"您需要走的路程= "<<way[a][b]<<endl;// cout<<"\t\t\t\t"<<"从"<<site[a]<<"到"<<site[b]<<"的最短距离是:"<<Dist[b]<<endl; printf("\t\t\t\t路径如下:\n");// printf("\t\t\t\t"); // cout<<site[a]<<"---->";// print(b);// }else{ cout<<"输入的位置错误或不存在！！！\n"; } } else{ cout<<"输入的位置错误或不存在！！！\n"; } } system("pause"); } void map()//地图 { system("color 70"); system("time/t"); system("date/t"); cout<<" 南阳理工景点精简小地图 \n"; cout<<" (23) (16) \n"; cout<<" * * * * * * * * *体育馆* * * * * * *图书馆 \n"; cout<<" ||东 (18)* * (5) || * \n"; cout<<" ||门 * * || * \n"; cout<<" * (12) 体育场 || * \n"; cout<<" 南苑 ******** （东南）|| 齐 \n"; cout<<" 餐厅 * || 贤 （10） ____ \n"; cout<<" ** (15) * || 广 * * * * * * *南门* * * * * * * \n"; cout<<" ** * || 场 （20）** \n"; cout<<" (25)** * || （15） * ** \n"; cout<<" * * * *书香园* * * * * * * * * \n"; cout<<" || **（25） ** 四环广场** \n"; cout<<" ||校 ** （25）** ** （10） \n"; cout<<" ||内 **教工 ** ** \n"; cout<<" ||的 三村** ** * \n"; cout<<" ||一 ** ** *学苑餐厅 \n"; cout<<" ||条 (8) **体育场 ** \n"; cout<<" ||不 （西北） ** (12) \n"; cout<<" ||知 ** * * *领创空间* \n"; cout<<" ||名 (10) * \n"; cout<<" ||的 *(10) \n"; cout<<" ||河 * \n"; cout<<" || 北大门 \n"; cout<<" ————— \n"; puts("\n\n\n\n\t\t\t\t\t\t\t\t\t\t\t南阳理工学院校园导航\n"); puts("\t\t\t\t\t\t\t\t\t\t\t\t---Java1班--周文豪"); system("pause"); } void introduce()//介绍各个地方信息的函数 { puts("\n\n\n\n\n"); printf("\t\t\t\t ~ ~ ~ ~ ~ ~ ~