城市交通导航最短路径查询

2023-11-30 09:43| 来源: 网络整理| 查看: 265

导航最短路径查询系统

上学期期末老师让写一个课程设计，给了很多课题，选了导航最短路径查询系统，题目如下： 1 项目简介

设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。最短路径问题的提出随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。而网络分析中最基本和关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间一般在1s-3s，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。最优路径问题不仅包括最短路径问题，还有可能涉及到最少时间问题、最少收费（存在收费公路）问题、或者是几个问题的综合，这时将必须考虑道路级别、道路流量、道路穿越代价（如红灯平均等待时间）等诸多因素。但是必须指出的是，一般来说最优路径在距离上应该是最短的，但最短路径在行驶时间和能源消耗的意义上未必是最优的。其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。 2 设计思路

单源最短路径算法的主要代表之一是Dijkstra（迪杰斯特拉）算法。该算法是目前多数系统解决最短路径问题采用的理论基础，在每一步都选择局部最优解，以期望产生一个全局最优解。 Dijksira算法的基本思路是：对于图G=(V,E)，V是包含n个顶点的顶点集，E是包含m条弧的弧集，(v, w)是E中从v到w的弧，c(v, w)是弧(v, w)的非负权值，设s为V中的顶点，t为V中可由s到达的顶点，则求解从s至t的具有最小弧权值和的最短路径搜索过程如下： (1) 将v中的顶点分为3类：已标记点、未标记点、己扫描点。将s初始化为己标记点，其它顶点为未标记点。为每个顶点v都建立一个权值d和后向顶点指针p，并将d初始化如下：d(v)=0，v=s；d(v)=∞，v≠s。 (2) 重复进行扫描操作：从所有已标记点中选择一个具有最小权值的顶点v并将其设为己扫描点，然后检测每个以v为顶点的弧(v, w)，若满足d(v) + c(v, w) < d(w) 则将顶点v设为已标记点，并令d(w) = d(v) + c(v, w), p(w) = v。 (3) 若终点t被设为已扫描点，则搜索结束。由t开始遍历后向顶点指针P直至起点s，即获得最短路径解。 3 数据结构

（1）定义一个数组min_dist，它的每个数组元素min_dist[i]表示当前所找到的从始点vi到每个终点vj的最短路径的长度。它的初态为：若从vi到vj有边，则min_dist[j]为边的权值；否则置min_dist[i]为∞。定义一个数组path，其元素path[k]（0≤k≤n-1）用以记录vi到vk最短路径中vk的直接前驱结点序号，如果vi到vk存在边，则path[k]初值为i。定义一个数组W，存储任意两点之间边的权值。　（2）查找min(min_dist[j]，j∈V-S)，设min_dist[k]最小，将k加入S中。修改对于V-S 中的任一点vj，min_dist[j]=min(min_dist[k]+w[k][j], min_dist[j]) 且path[j]=k。　（3）重复上一步，直到V-S为空。　　在算法设计时，用一个tag数组来记录某个顶点是否已计算过最短距离，如果tag[k]=0，则vk∈V-S，否则vk∈S。初始值除tag[i]=1以外，所有值均为0。

路径图如下：在这里插入图片描述迪杰斯特拉算法流程图如下：

弗洛伊德算法流程图如下：在这里插入图片描述

代码总体结构图如下：在这里插入图片描述

在写代码期间也遇到了好多的问题，反反复复改了好多次，代码如下：

#include #include #include #define INFINITY 50000 #define MAXVERTEX 35 #define NAMESLEN 20 typedef char VRType; typedef int AdjMatrix; typedef struct { VRType city[50]; int id; }VertexType; typedef struct{ VertexType vex[MAXVERTEX];//城市 AdjMatrix arcs[MAXVERTEX][MAXVERTEX];//用于存放城市之间路径的矩阵 int vexnum,arcnum;//图中的城市数量和路径的数量 }Mgraph; typedef int Pathmatirx[MAXVERTEX][MAXVERTEX];// 二维数组用于弗洛伊德算法中存放经过的城市的id typedef int ShortPathTable[MAXVERTEX][MAXVERTEX];//用于存放最短路径上城市的距离 typedef enum { FALSE, TRUE }boolean;//用来判断跳出管理模式 int is_exitx(Mgraph G,char city[]); int Transform_id(Mgraph G,char city[]); void CreateGraph(Mgraph &G); void ShortestPath_DIJ(Mgraph G,int v0); void ShortestPath_FLOYD(Mgraph G,Pathmatirx &P, ShortPathTable &D); void addPath(Mgraph &G,int anum); void Traversal(Mgraph &G); void addCityandPath(Mgraph &G); void Delete(Mgraph &G); int modPath(Mgraph &G,int path_s); void modCity(Mgraph &G); void System(Mgraph &G); int is_exitx(Mgraph G,char city[])//判断城市是否存在的方法，存在返回1否则返回0 { int flag=0; for(int i = 0;i flag=1; break; } } return flag; } int Transform_id(Mgraph G,char city[])//获取城市id的函数，后面会频繁用到 { int i,id; for(i=0;i id=G.vex[i].id; } } return id; } void CreateGraph(Mgraph &G)//创建城市交通图 { G.vexnum = 25; //交通图中初始化城市的数量 G.arcnum = 30; //交通图中初始化路径的数量 int a,d,e,f,g,i,j,w,num; char b[NAMESLEN],c[NAMESLEN]; for(i=0;i for(int j=0;j int D[MAXVERTEX],P[MAXVERTEX]; int v,u,i,j,k,w,min,a,v0; char name[10]; int final[MAXVERTEX];//用于判断城市是否已经访问 char *id[MAXVERTEX];//定义一个字符串数组用于正向输出路径 id[0]='\0';//初始化数组为空 printf("请输入起点城市\n"); scanf("%s",&name); while(!is_exitx(G,name)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name); } v0=Transform_id(G,name); for(v=0;v P[v]=v0; } else{ P[v]=0; } } P[v0]=-1;//用来后面判断正序输出是否到起点 D[v0]=0;//起点到起点的路径设为0； final[v0]=1;//访问过就变为1 for(i=0; i if(!final[w]&&D[w] if(!final[w]&&(min+G.arcs[u][w]//此循环用于输出v0到各个城市所经过的城市 if(i!=v0)//v0到v0没有路径 { if(D[i]==INFINITY) { printf("%s到%s之间没有路径\n",G.vex[v0].city,G.vex[i].city); } else{ j=0; printf("%s到%s最短路径长度为：%d\n",G.vex[v0].city,G.vex[i].city,D[i]); v=P[i];//中间变量v就等于该城市的前一个城市 printf("路径为：%s->",G.vex[v0].city); if(v!=-1)//因为如果v0的节点为零，再途径v0的城市不能输出v0，所以改为-1 { while(v!=-1)//逐个输出途径城市，但是路径是倒叙 { id[j] = G.vex[v].city;// 将城市的名称存放在字符串数组id【】中，用于正序输出 j++;//输入向后移动一个空间 v=P[v];//继续向前找途径城市 } j=j-1;//最后一为数组值为'\0'，所以要减一 k=j;//判断循环 for(int f=0;f int c,d,v,w,u,temp; char a[NAMESLEN],b[NAMESLEN];//用于输入起点和终点城市 for(v=0;v D[v][w]=G.arcs[v][w];//两个城市之间的路径赋值 P[v][w]=w;//设前一个城市为w } } for(u=0;u for(w=0;w D[v][w]=D[v][u]+D[u][w]; P[v][w]=P[v][u]; } } } } printf("请输入起点城市：\n");//需要知道起点和终点城市是否存在！！！！ scanf("%s",&a); while(!is_exitx(G,a)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&a); } printf("请输入终点城市：\n"); scanf("%s",&b); while(!is_exitx(G,b)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&b); } c=Transform_id(G,a); d=Transform_id(G,b); if(D[c][d]==INFINITY)//如果两个城市没有路径 { if(c!=d) { printf("%s到%s之间没有路径！",a,b); } } else { printf("%s到%s之间最短路径为：%d\n",G.vex[c].city,G.vex[d].city,D[c][d]); temp=P[c][d]; printf("路径：%s",G.vex[c].city); while(temp!=d)//同迪杰斯特拉一样，只不过此次输出的就是正序 { printf("->%s",G.vex[temp].city); temp=P[temp][d]; } printf("->%s\n",G.vex[d].city); } printf("======================================================================\n"); printf("======================================================================\n"); } //只增加路径 void addPath(Mgraph &G,int anum)//增加路径函数要判断城市是否存在 { int i,j; int a,b,pathlong; char name1[10],name2[10]; for(i=0; i printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name1); } printf("请输入增加第%d条路径的终点城市：\n",i+1); scanf("%s",&name2); while(!is_exitx(G,name2)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name2); } a = Transform_id(G,name1); b = Transform_id(G,name2); if(G.arcs[a][b]==INFINITY) { printf("%s与%s间无路径，可以添加\n", name1,name2); printf("请输入路径长度:\n"); scanf("%d",&pathlong); G.arcs[a][b] = pathlong; G.arcs[b][a] = pathlong; printf("添加成功！\n"); } else { printf("%s与%s间已有路径，无法添加\n", name1,name2); } printf("====================================================================\n"); printf("====================================================================\n"); } } void Traversal(Mgraph &G)//遍历所有城市信息输出矩阵 { int a = 0; //printf("===================================================================="); //printf("===================================================================="); //printf("====================================================================\n"); printf("===============各城市名称和对应编号===============\n"); for(int i=0;i printf("\n"); printf("--------------------------------------------------\n"); } printf("|%8s--%2d| ",G.vex[i].city,i); } printf("\n==================================================\n"); printf("城市编号及对应矩阵图\n"); printf(" 编号 "); for(int i=0;i printf("|%4d|",G.vex[i].id); for(int j=0;j printf("|%4d|", G.arcs[i][j]); } else{ printf("| ∞ |"); } } printf("\n"); printf("======================================================================\n"); printf("======================================================================\n"); } } void Delete(Mgraph &G)//删除城市和路径 { int a=0,i,j; char name[10]; printf("请输入需要删除城市的名称：\n"); scanf("%s",&name); while(!is_exitx(G,name)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name); } for( i=0;i a = G.vex[i].id; break; } } G.vexnum=G.vexnum-1;//顶点数目减1 for( i=a;i G.vex[i].id = i; } for( i = a;i if(j G.arcs[i][j] = G.arcs[i+1][j+1]; } } } for(i=a;i G.arcs[j][i] = G.arcs[i][j]; } } printf("删除成功！\n"); } void addCityandPath(Mgraph &G)//添加城市和路径要判断城市是否重复添加 { int i,j,k,a,b,pathlong; char name[10]; char name1[10],name2[10]; int vnum,anum; // printf("请输入添加城市的数量：\n"); // scanf("%d",&vnum); printf("请输入添加城市的名称\n"); // for(i=0; i printf("你输入的城市已存在，请重新输入：\n"); scanf("%s",&name1); } G.vex[k].id=k; strcpy(G.vex[k].city,name); for(j=0; j //pathlong = 0; printf("请输入增加第%d条路径的起点城市：\n",i+1);//判断城市是否存在！！！！ scanf("%s",&name1); while(!is_exitx(G,name1)){ printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name1); } printf("请输入增加第%d条路径的终点城市：\n",i+1); scanf("%s",&name2); while(!is_exitx(G,name2)){ printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name2); } a = Transform_id(G,name1);//获取id b = Transform_id(G,name2); if(G.arcs[a][b]==INFINITY)//没有路径才能够添加 { printf("%s与%s间无路径，可以添加\n", name1,name2); printf("请输入路径长度:\n"); scanf("%d",&pathlong); G.arcs[a][b] = pathlong; G.arcs[b][a] = pathlong; printf("添加成功！\n"); } else { printf("%s与%s间已有路径，无法添加\n", name1,name2); } } } void modCity(Mgraph &G)//修改城市的名称 { char name1[10],name2[10]; int a; printf("请输入需要修改的城市的名称：\n"); scanf("%s",&name1); while(!is_exitx(G,name1)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name1); } for( int i=0;i a = G.vex[i].id; break; } } printf("请输入修改过后的城市的名称：\n"); scanf("%s",&name2); while(is_exitx(G,name2))//判断城市名称是否已经存在 { printf("你输入的城市已存在，请重新输入：\n"); scanf("%s",&name2); } strcpy(G.vex[a].city,name2); printf("修改成功！\n"); } int modPath(Mgraph &G,int path_s)//修改路径长度 { char name1[10],name2[10]; int a,b,newpath; for(int i=0;i printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name1); } printf("请输入增加第%d条路径的终点城市：\n",i+1); scanf("%s",&name2); while(!is_exitx(G,name2)) { printf("你输入的城市不存在，请重新输入：\n"); scanf("%s",&name2); } a = Transform_id(G,name1); b = Transform_id(G,name2); if(G.arcs[a][b]!=INFINITY) { printf("请输入修改后的路径长度：\n"); scanf("%d",&newpath); G.arcs[a][b]=newpath; G.arcs[b][a]=newpath; printf("修改成功！\n"); } else { printf("%s与%s之间没有路径，无法修改。\n",name1,name2); printf("已为您退出到管理界面\n"); } } } void System(Mgraph &G){ Pathmatirx P; ShortPathTable D; char a[NAMESLEN]; char *password="1"; char b; boolean T; while(1) { T =TRUE ; int i=3; printf("\n----------------------------------------------------------------------\n"); printf("*************************导航最短路径查询系统*************************\n"); printf("======================================================================\n"); printf("=============== 1.求一个城市到其他所有城市的最短路径 =================\n"); printf("=============== 2.求某个城市到另一个城市的最短路径 =================\n"); printf("=============== 3.进入管理模式 =================\n"); printf("=============== 0.退出咨询系统 =================\n"); printf("======================================================================\n"); printf("请输入您的选择： "); scanf("%s", &b);//如果输入的是字符怎么办 getchar(); switch(b) { case '1': printf("计算起点到各个顶点的最短路径。\n"); ShortestPath_DIJ(G); break; case '2': printf("计算一个点到另一个点的最短路径\n"); ShortestPath_FLOYD(G,P,D); break; case '3': while(i>0) { printf("请输入管理员密码：\n"); char password1[10]; gets(password1); i--; if((!strcmp(password,password1))) { char choic; i=0; printf("=========================================\n"); printf("========= 已进入管理模式 ==========\n"); while(T){ printf("========= 1.增加城市和路径 ==========\n"); printf("========= 2.只增加路径 ==========\n"); printf("========= 3.修改已有城市名称 ==========\n"); printf("========= 4.修改已有城市路径 ==========\n"); printf("========= 5.删除已有城市 ==========\n"); printf("========= 6.输出城市路径矩阵 ==========\n"); printf("========= 0.退出管理模式 ==========\n"); printf("=========================================\n"); scanf("%s",&choic); switch(choic) { case '1': addCityandPath(G); break; case '2': int num_s; printf("请输入增加的路径数量:\n"); scanf("%d",&num_s); addPath(G,num_s); break; case '3': modCity(G); break; case '4': int path_s; printf("请输入需要修改路径的数量:\n"); scanf("%d",&path_s); modPath(G,path_s); break; case '5': Delete(G); break; case '6': Traversal(G); break; case '0': printf("已退出管理模式\n"); printf("======================================================================\n"); T = FALSE; break; default: printf("输入有误！请输入正确的选择：\n"); } } } else{ printf("密码错误，你还有%d次机会\n",i); } } break; case '0': printf("退出系统！\n"); exit(-1); break; default: printf("输入有误，请重新输入\n"); break; } } } int main() { Mgraph G; printf("======================================================================\n"); printf("=============== 创建交通图 =================\n"); CreateGraph(G); printf("=============== 交通图建立完毕 =================\n"); printf("======================================================================\n"); System(G); return 0; } **编译用的DEV C++，也测试了很多次，代码比较简单，有问题请留言。**

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章