1、信息科学与工程学院课 程 设 计 任 务 书题 目： 交通咨询系统设计 学 号： 201112220141 姓 名： 年 级： 专 业： 计算机应用与技术课 程： 数据结构 指导教师： 职 称： 完成时间： 课程设计任务书及成绩评定课程设计的任务和具体要求设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两个城市顶点之间的最短路径问题。指导教师签字： 日期： 指导教师评语：成绩： 指导教师
2、签字： 日期： 课程设计所需软件、硬件等PC 兼容机、Windows 操作系统、Turbo C/Win t、Vc+软件等。课 程 设 计 进 度 计 划起止日期 工作内容 备注参考文献、资料索引（序号、文献名称、编著者、出版单位）数据结构（C 语言版） 编著 严蔚敏 吴伟民 清华大学出版社 1997数据结构 中国石油大学出版社一、需求分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三是实现任两
3、个城市顶点之间的最短路径问题。1.1.1 建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的 n 阶方阵：设 G=（V，E）是一个图，结点集为 nvV,21。G 的邻接矩阵 ,E,0)(,)( jiji jijinjiijnij vwaA） 或当 （，或 ） 或当 （，当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有 n 个元素的一维数组来存储顶点信息，其中下标为 i 的元素存储顶点 i 的信息。因此，图的邻接矩阵的存储结构定义如下：#defin
4、f MVNum 50 /最大顶点数typedef structVertexType vexsMVNum; /顶点数组，类型假定为 char 型Adjmatrix arcsMVNumMVNum; /邻接矩阵，假定为 int 型MGraph;1.1.2 单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权） ，我们希望找出从某个源点 S V 到 G 中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉
5、算法。迪杰斯特拉算法求最短路径的实现思想是：设 G=（V，E）是一个有向图，结点集为， ，cost 是表示 G 的邻接矩阵，costij表示有v,Vn21向边的权。若不存在有向边，则 costij的权为无穷大（这里取值为 32767） 。设 S 是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点 v1为源点，集合 S 的初态只包含一个元素，即顶点 v1。数组 dist 记录从源点到其他顶点当前的最短距离，其初值为disti=costv1i,i=1,2,n。从 S 之外的顶点集合 V-S 中选出一个顶点 w，使 distw的值最小。于是从源点到达 w 只通过 S
6、中顶点，把 w 加入集合S 中，调整 dist 中记录的从源点到 V-S 中每个顶点 v 的距离：从原来的 distv和distw+costwv中选择较小的值作为新的 distv。重复上述过程，直到V-S 为空。最终结果是：S 记录了从源点到该顶点存在最短路径的顶点集合，数组dist 记录了源点到 V 中其余各顶点之间的最短路径，path 是最短路径的路径数组，其中 pathi表示从源点到顶点 i 之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化 S 和 D，置空最短路径终点集，置初始的最短路径值；Sv1=TRUE; Dv1=0； /S 集初始时只有源点，源点到源点的
7、距离为0；While (S 集中顶点数和是否存在。如果存在，则比较和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于 1 的最短路径。其次，考虑从 vi到vj是否包含有顶点 v2为中间顶点的路径，若没有，则说明从vi到 vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1 的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从 vi到 vj的中间顶点序号不大于 1 的最短路径比较，取其长度较短者作为当前求得的从 vi到 vj的中间顶点序号不大于 2 的最短路径。依此类推，直到顶点 vn加入当前从
8、 vi到 vj的最短路径后，选出从 vi到 vj的中间顶点序号不大于 n 的最短路径为止。由于图 G 中顶点序号不大于 n，所以 vi到 vj的中间顶点序号不大于 n 的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是 vi到 vj的最短路径。1.2 程序流程图二、详细设计2.1 建立有向图的存储结构void CreateMGraph(MGraph * G,int n,int e)int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;iarcsij=Maxint;printf(“输入%d 条边的 i,j 及 w:n“,e);for(k=1;karcs
9、ij=w;printf(“有向图建立完毕n“);2.2 迪杰斯特拉算法void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;if(D2varcsvwarcsvw;P2w=v;printf(“路径长度 路径n“);for(i=1;iarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij)D
10、ij=Dik+Dkj;Pij=Pik;2.4 运行主控程序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(“1.求一个城市到所有城市的最短路径n“);printf(“2.求任意的两个城市之间的最短路径n“);printf(“ 请选择：1 或 2,选择 0 退出:“);scanf(“%d“,
