交通咨询系统设计

《数据结构》课程设计报告

题目——交通咨询系统设计

班 级： 学 号： 姓 名： 时 间：

一、设计目的与内容

1．设计目的

充分了解并掌握最短路径问题及其应用，根据有向图的存储结构解决实际问题。 2．设计内容：

任务：设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。 要求：

1）建立交通网络网的存储结构。 2）提供程序测试方案。 3）界面友好。

二、 算法的基本思想

实验分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。 1． 建立图的存储结构

首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩

阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

Wij，若(vi,vj)或vi,vjE(G);A[i，j]=

0或，当不满足上述条件时。 一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数

组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维

数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息

2． 单源最短路径

初始化S和D，置空最短路径终点集，置初始的最短路径值；

S[v1]=TRUE；D[v1]=0；//S集初始时只有源点，源点到源点的距离为0； while（S集中顶点数开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中； S[v]=TRUE；

更新当前最短路径及距离；

}

3． 任意一对顶点间最短路径

假设求从顶点vi到vj的最短路径。如果从vi到vj存在一条长度为arcs[i][j]

的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径〈vi，v1〉和〈v1，vj〉是否存在。如果存在，则比较路径〈vi，vj〉和〈vi，v1，vj〉的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径〈vi，…，v2，…，vj〉，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么〈vi，…，v2，…，vj〉可分解为〈vi，…，v2〉和〈v2，…，vj〉，而这两条路径是前一次找到的

中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径〈vi，…，v2，…，vj〉的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于2的最短路径。依次类推，直至顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。

三、测试数据

输入图中顶点个数和边数n，e: 7,10 输入10条边的i,j及w: 1,7,9 2,1,20 2,3,10 2,4,30 3,5,5 5,4,12 5,7,15 6,5,8 6,7,10

7,3,18

有向图的存储结构建立完毕!

******求城市之间的最短路径******

============================================ 1.求一个城市到所有城市的最短路径 2.求任意的两个城市之间的最短路径

============================================ 请选择: 1 或 2,选择 0 退出: 1 求单源路径,输入源点 v: 1 路径长度 路径 0 1 32767 2

27 3<-7<-1

44 4<-5<-3<-7<-1 32 5<-3<-7<-1 32767 6

9 7<-1

******求城市之间的最短路径******

============================================ 1.求一个城市到所有城市的最短路径 2.求任意的两个城市之间的最短路径

============================================ 请选择: 1 或 2,选择 0 退出: 2 dij=29,pij=1

dij=15,pij=3 dij=23,pij=3 dij=27,pij=3 dij=17,pij=5 dij=20,pij=5 dij=20,pij=5 dij=35,pij=3 dij=38,pij=3 dij=27,pij=7 dij=44,pij=7 dij=32,pij=7 dij=38,pij=5 dij=33,pij=7 dij=38,pij=7

dij=28,pij=7

输入源点(或称起点)和终点：v,w: 2,4

从顶点2到4的最短路径是: 2->3->5->4路径长度: 27 ******求城市之间的最短路径******

============================================ 1.求一个城市到所有城市的最短路径 2.求任意的两个城市之间的最短路径

============================================ 请选择: 1 或 2,选择 0 退出: 2 dij=29,pij=1 dij=15,pij=3 dij=23,pij=3 dij=27,pij=3 dij=17,pij=5 dij=20,pij=5 dij=20,pij=5 dij=35,pij=3 dij=38,pij=3 dij=27,pij=7 dij=44,pij=7 dij=32,pij=7 dij=38,pij=5 dij=33,pij=7

dij=38,pij=7 dij=28,pij=7

输入源点(或称起点)和终点：v,w: 1,4

从顶点1到4的最短路径是: 1->7->3->5->4路径长度: 44 ******求城市之间的最短路径******

============================================ 1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

============================================ 请选择: 1 或 2,选择 0 退出: 0

四、源程序及系统文件使用说明

#include #include #define MVNum 100 #define Maxint 32767 enum boolean{FALSE,TRUE}; typedef char VertexType; typedef int Adjmatrix; typedef struct{

VertexType vexs[MVNum];

Adjmatrix arcs[MVNum][MVNum]; }MGraph;

int D1[MVNum],P1[MVNum];

int D[MVNum][MVNum],P[MVNum][MVNum]; void CreateMGraph(MGraph *G,int n,int e); void Dijkstra(MGraph *G,int v1,int n); void Floyd(MGraph *G,int n); void main() { MGraph *G; int m,n,e,v,w,k;

int xz=1;

G=(MGraph *)malloc(sizeof(MGraph)); printf(\"输入图中顶点个数和边数n，e: \"); scanf(\"%d,%d\ CreateMGraph(G,n,e);

while(xz!=0){

printf(\"******求城市之间的最短路径******\\n\");

printf(\"============================================\\n\"); printf(\"1.求一个城市到所有城市的最短路径\\n\"); printf(\"2.求任意的两个城市之间的最短路径\\n\");

printf(\"============================================\\n\"); printf(\"请选择: 1 或 2,选择 0 退出: \"); scanf(\"%d\ if(xz==2){

Floyd(G,n);

printf(\"输入源点(或称起点)和终点：v,w: \"); scanf(\"%d,%d\ k=P[v][w]; if(k==0)

printf(\"顶点%d 到 %d 无路径!\\n\

else {

printf(\"从顶点%d到%d的最短路径是: %d\ while(k!=w){ printf(\"->%d\ k=P[k][w];

}

printf(\"->%d\

printf(\"路径长度: %d\\n\ } }

else

if(xz==1){

printf(\"求单源路径,输入源点 v: \"); scanf(\"%d\

Dijkstra(G,v,n); } }

printf(\"结束求最短路径,再见! \\n\"); }

void CreateMGraph(MGraph *G,int n,int e) {

int i,j,k,w;

for(i=1;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++)

G->arcs[i][j]=Maxint;

printf(\"输入%d条边的i,j及w: \\n\ for(k=1;k<=e;k++){

scanf(\"%d,%d,%d\

G->arcs[i][j]=w; }

printf(\"有向图的存储结构建立完毕!\\n\"); }

void Dijkstra(MGraph *G,int v1,int n) { int D2[MVNum],P2[MVNum]; int v,i,w,min;

enum boolean S[MVNum]; for (v=1;v<=n;v++){ S[v]=FALSE; D2[v]=G->arcs[v1][v]; if(D2[v]P2[v]=v1; P2[v]=0; else

}

D2[v1]=0;S[v1]=TRUE; for(i=2;ifor(w=1;w<=n;w++) if(!S[w]&&D2[w]{v=w;min=D2[w];} S[v]=TRUE;

for(w=1;w<=n;w++) if(!S[w]&&(D2[v]+G->arcs[v][w]arcs[v][w];

}

P2[w]=v;

}

printf(\"路径长度 路径\\n\"); for(i=1;i<=n;i++){ printf(\"%5d\

printf(\"%5d\ while(v!=0){ printf(\"<-%d\ v=P2[v]; }

printf(\"\\n\"); } }

void Floyd(MGraph *G,int n) {

int i,j,k,v,w;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {

if(G->arcs[i][j]!=Maxint) P[i][j]=j; else

}

P[i][j]=0;

D[i][j]=G->arcs[i][j]; }

for(k=1;k<=n;k++) { }

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{ if(D[i][k]+D[k][j]P[i][j]=P[i][k];

printf(\"dij=%d,pij=%d\\n\

五、心得体会

通过本次实验，充分了解掌握了最短路径问题，并结合图的储存结构、迪杰斯特拉算法、

费洛依德算法等解决了交通咨询系统的设计。源程序打出来后有多处错误，大小写错误、符号错误、遗漏等等，经反复检查调试后实验成功。

六、参考文献

1．《数据结构（C语言版）》 严蔚敏，吴伟民 清华大学出版社