题目五：交通咨询系统设计

设计要求：

设计一个咨询交通系统，能让旅客咨询从任一个城市到另一个城市之间的最短路径（里程）、最低费用或者最少时间等问题。对于不同的咨询要求，可以输入城市间路程、所需时间或者所需费用。

设计分3个部分：

1、 建立交通网络图的存储结构；

2、 解决单源最短路径问题；

3、 实现两个城市之间的最短路径问题。

1、直接用二维数组存放图的信息

注意图是有向图还是无向图

void build(int e[][10],int n,int m){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)e[i][j]=(i==j)?0:inf;for(int i=1;i<=m;i++){int t1,t2,d;//位置t1到位置t2的距离是d cin>>t1>>t2>>d;e[t1][t2]=e[t2][t1]=d;//无向图 }}

2、单源最短路Dijkstra算法

最近意识到经常因为阅读一些理论性的东西，导致实际学习效率变得非常低（因为常常理论性的文章不好读懂，且本人看一大段文章的时候容易走神）

现在越发觉得，很多关于算法的题目知识点什么的直接看代码，在做题中巩固实际上是效率很高的一种学习方法，所以我也不叨叨什么单源多源最短路的实现思想了

直接上代码，就是看着代码学，看着代码找感觉（当然稍微还是要明白一些背景知识的，不要死磕，知道大体什么意思，直接刚代码）

单源最短路：找出一个点到其他所有点的最短路

void Dijkstra(int e[][10],int n)//贪心思想{int dis[10],book[10]; //所求结点到其他结点的最短路 记录当前结点是否已经判断过了//初始化单源最短数组dis,这里是1号顶点到其余各顶点的初始路径for(int i=1; i<=n; i++)dis[i]=e[1][i];for(int i=2; i<=n; i++)book[i]=0;//未知最短路顶点book[1]=1;//Dijkstra 算法核心语句for(int i=1; i<=n-1; i++) {int min=inf,t;for(int j=1; j<=n; j++)if(book[j]==0&&dis[j]<min) {//找出未判断结点中到1号结点（单源最短路起点）距离最小结点min=dis[j];t=j;}book[t]=1;//及时将选出的该结点标记为已判断过了for(int v=1; v<=n; v++) {//判断其他结点借助当前选出的结点，是否使得到1号结点的距离变短if(e[t][v]<inf) {if(dis[v]>dis[t]+e[t][v])dis[v]=dis[t]+e[t][v];//记录借助当前选出结点使得到1号结点更短路径的新距离}}}cout<<"所求城市单源最短路径为:"<<endl;for(int i=2; i<=n; i++)cout<<citys[1]<<"->"<<citys[i]<<": "<<dis[i]<<endl;}

3、多源最短路Floyd算法

void Floyd(int e[][10],int n)//多源最短路{for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)for(int k=1; k<=n; k++)if(e[i][k]+e[k][j]<e[i][j])e[i][j]=e[i][k]+e[k][j];for(int i=1; i<=n; i++)cout<<"\t"<<citys[i];cout<<endl;for(int i=1; i<=n; i++) {cout<<citys[i];for(int j=1; j<=n; j++)printf("%8d",e[i][j]);cout<<endl;}}

4、直接完整代码好了

#include <bits/stdc++.h>using namespace std;const int inf=0x3f3f3f3f;string citys[10]= {"0","北京","西安","郑州","徐州","成都","广州","上海"};void build(int e[][10],int n,int m){for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)e[i][j]=(i==j)?0:inf;for(int i=1; i<=m; i++) {int t1,t2,d;//位置t1到位置t2的距离是dcin>>t1>>t2>>d;e[t1][t2]=e[t2][t1]=d;//无向图}}void Floyd(int e[][10],int n)//多源最短路{for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)for(int k=1; k<=n; k++)if(e[i][k]+e[k][j]<e[i][j])e[i][j]=e[i][k]+e[k][j];for(int i=1; i<=n; i++)cout<<"\t"<<citys[i];cout<<endl;for(int i=1; i<=n; i++) {cout<<citys[i];for(int j=1; j<=n; j++)printf("%8d",e[i][j]);cout<<endl;}}void Dijkstra(int e[][10],int n)//贪心思想{int dis[10],book[10]; //所求结点到其他结点的最短路 记录当前结点是否已经判断过了//初始化单源最短数组dis,这里是1号顶点到其余各顶点的初始路径for(int i=1; i<=n; i++)dis[i]=e[1][i];for(int i=2; i<=n; i++)book[i]=0;//未知最短路顶点book[1]=1;//Dijkstra 算法核心语句for(int i=1; i<=n-1; i++) {int min=inf,t;for(int j=1; j<=n; j++)if(book[j]==0&&dis[j]<min) {//找出未判断结点中到1号结点（单源最短路起点）距离最小结点min=dis[j];t=j;}book[t]=1;//及时将选出的该结点标记为已判断过了for(int v=1; v<=n; v++) {//判断其他结点借助当前选出的结点，是否使得到1号结点的距离变短if(e[t][v]<inf) {if(dis[v]>dis[t]+e[t][v])dis[v]=dis[t]+e[t][v];//记录借助当前选出结点使得到1号结点更短路径的新距离}}}cout<<"所求城市单源最短路径为:"<<endl;for(int i=2; i<=n; i++)cout<<citys[1]<<"->"<<citys[i]<<": "<<dis[i]<<endl;}void Inquiry(int e[][10],int n){int i;string t;cout<<"请输入你要查询的城市名：";cin>>t;for(i=1; i<=n; i++) {if(citys[i]==t)break;}if(i==n+1) {cout<<endl<<"所查城市不在交通网络图中"<<endl;return ;}cout<<endl<<"所求城市"<<citys[i]<<"单源最短路径为:"<<endl;for(int j=1; j<=n; j++) {if(i==j) continue;cout<<citys[i]<<"->"<<citys[j]<<": "<<e[i][j]<<endl;}}void menu(){int e[10][10];int n,m;//顶点个数 边的个数cin>>n>>m;build(e,n,m);Floyd(e,n);Dijkstra(e,n);Inquiry(e,n);Inquiry(e,n);}int main(){freopen("data.txt","r",stdin);menu();return 0;}

附带的测试数据：

7 101 2 25531 3 6951 4 7042 3 5112 5 8123 4 3493 6 15794 7 6515 6 23686 7 1385徐州青岛

5、用邻接矩阵且用文件形式读入数据

#include<stdio.h>#include<stdlib.h>#define Vertex_NUM 50// 最大顶点数#define INF 32767// 无穷大∞//邻接矩阵的类型定义如下：typedef struct {int no;//顶点编号char info;//顶点其他信息} VertexType;//顶点类型typedef struct {VertexType vexs[Vertex_NUM];//存放顶点信息int arcs[Vertex_NUM][Vertex_NUM];//邻接矩阵的边数组intvn, en;//顶点数，边数} MGraph;//完整的图邻接矩阵类型void readfromDisk(MGraph *G){// 从磁盘读取数据inti, j, w;char ch = 'A';// 任意值FILE *inp;inp = fopen("data.in", "r");if(inp <= 0) {printf("\ndata.in文件不存在！请创建data.in文件吧！\n");exit(0);}fseek(inp, 0, SEEK_SET);printf("\n你所给定的图G各弧的权值为：\n");while(ch != EOF) {fscanf(inp, "%d %d %d", &i, &j, &w);G->arcs[i][j] = w;printf("<%d %d %d>\n", i, j, w);ch = fgetc(inp);}fclose(inp);}MGraph *CreateMGraph(){int i, j, w;MGraph *G;G = (MGraph *)malloc(sizeof(MGraph));//建立图的存储结构printf("\n输入图G的顶点个数 N = ");scanf("%d", &G->vn);for(i = 1; i <= G->vn; i++) {G->vexs[i].no = i;}for(i = 1; i <= G->vn; i++)for(j = 1; j <= G->vn; j++)G->arcs[i][j] = INF;readfromDisk(G);printf("\n图的存储建立完毕!\n");returnG;}int main(){MGraph *G;G = CreateMGraph();return 0;}

ㄟ( ▔, ▔ )ㄏ

如果觉得《【数据结构课程设计】题目五：交通咨询系统设计（经典最短路问题）》对你有帮助，请点赞、收藏，并留下你的观点哦！