《数据结构课程设计》最短路径问题实验报告》可供会员共享，在线阅读。 更多相关《数据结构课程设计》最短路径问题实验报告(17页珍藏版)》请在人人文库网搜索。
1、目录一、简介1二、系统分析1三、简介设计2四、详细设计54.1制图记忆结构54.2单源最短路径64.3任意一对顶点之间最短路径7五、运行与测试8参考文献11附录12交通咨询系统设计(最短路径问题)一、交通网络越来越发达系统中用图构建各城市之间的联系，图中的顶点表示城市，边表示各城市之间的交通关系，权重是两个城市之间的成本。 这个交通咨询系统可以回答旅客提出的各种问题。 例如，选择路径使得从a城到b城中途中继次数最少的方法； 如何选择路径，使a城到b城的距离最短； 如何选择将从a城到b城的费用控制在最小限度的路径等。
2、一系列问题。 二、系统分析可以设计交通咨询系统，咨询从一个城市顶点到另一个城市顶点的最短路线(距离)、最低费用或最低时间等问题。 对于每个呼叫要求，可以输入城市之间的距离、所需时间或所需费用等信息。 关于最短路径问题，为了解决实际的最短路径问题，本系统中使用了有关图的知识。 本系统包括作图的记忆结构、单源最短问题、任意一对顶点间最短路径问题三个问题，这些问题中使用了抖动算法和弗洛伊德算法。 本系统没有设置人性化的系统提示菜单，考虑了使用者的使用方便性。 三、概要设计可以将该系统大致分为三个部分。 1构建交通网络图存储结构； 2解决单源最短路径问题，实现三个城市的制高点。
3、之间的最短路径问题。 交通咨询系统的抖动算法(单源最短路径) wydxhd算法(任意顶点对最短路径)图的记忆结构义抖动算法流程图：弗洛伊德算法流程图：四、详细设计4.1图的记忆邻接矩阵是表示图形中顶点间的邻接关系的矩阵。 设G=(V，e )为具有n个顶点的图，则g的邻接矩阵是如下定义的n次方阵。 注：一个图的邻接矩阵表示是唯一的！ 表示需要以二维排列存储顶点间的邻接关系的邻接矩阵，需要以具有n个要素的一维排列存储顶点信息(下标为I的要素存储顶点的信息)。 相邻矩阵的存储结构： #define MVNum 100 /最大顶点数typedef structV。
4、ertexType vexsMVNum； 假设char型adj矩阵arcsmvnummvnum的顶点排列； /假设邻接矩阵，int型MGraph； 注：有向图的邻接矩阵不对称，运行程序时输入所有有向边及其权重即可。 4.2单源最短路径单源最短路径问题：有向图(加权)是已知的，最好找到从某个源点SV到g的其余各顶点的最短路径。 戴克斯特拉算法是按路径长度生成各顶点的最短路径算法。 算法思想：给出有向图g=(v，e )，其中v=1、2、n、cost是表示g的邻接矩阵，costij表示有向边的权重。 在不存在有向边的情况下，costij的权重无限大(这里设值为32767 )。 把s作为一个集合。
5，集合中的一个要素表示一个顶点，从源到这些顶点的最短距离已经求出。 以顶点V1为源点，集合s的初始状态只包含顶点V1。 数组dist记录从源到其他各顶点的当前最短距离，其初始值为disti=costij，i=2，n。 从s以外的顶点集合V-S中选择一个顶点w，使distw的值最小。 因此，要从源到达w，只通过s中的顶点，将w加到集合s中，调整从dist中记录的源到V-S中的各顶点v的距离：从原distv和distw costwv中选择较小的值作为新的distv。 重复上述过程，使s包含v的剩馀顶点的最短路径。 最终，s记录从源到该顶点的最短路径所在的顶点的集合，排列dist记录从源到v的那个。
6、其余各顶点之间的最短路径。 path是最短路径的路径排列，其中pathi表示从源到顶点I的最短路径的前驱顶点。 4.3任意一对顶点之间的最短路径任意顶点对之间的最短路径问题是，针对给定的有向网络图g=(v，e )，对g中的任意一对顶点有序地成对，作为“v，w ) VW”，找到从v到w的最短路径为了解决这个问题，可以以有向网络图中的各顶点为源点，通过重复执行n次前面的抖动算法，求出各对之间的最短路径。 hsdbd算法的基本思想：假设求出从Vi到Vj的最短路径。 如果有长度为arcsij的路径，则该路径不一定是最短路径，需要尝试n次。 首先考虑路径和是否存在。 如果存在，则通过比较路径和路径的路径长度来获取。
7、长短的现在被要求。 此路径是中间顶点编号为1以下的最短路径。 接着，考虑从vi到vj是否包含顶点v2为中间顶点的路径，如果不包含，则表示从vi到vj的当前最短路径是在前一步求出的； 如果有，可以分解为和。 这两个路径是最后找到的中间点编号小于或等于1的最短路径，将这两个路径的长度相加可以得到路径的长度。 将该长度与上次求出的从vi到vj的中间顶点编号为1以下的最短路径进行比较，将该长度较短的一方作为现在求出的从vi到vj的中间顶点编号为2以下的最短路径。 从现在开始，选择从vi到vj的中间顶点编号为n以下的最短路径，直到顶点vn加入到当前的从vi到vj的最短路径中。 图g中的顶点编号为n以下，因此从vi到vj的中间。
8、顶点编号为n以下的最短路径将所有顶点作为中间顶点进行了考虑
的可能性，因此，它就是vi到vj的最短路径。五、运行与测试3测试实例1：利用如下图所示的有向图来测试13177161747632646456262455测试实例2：利用下图求交通网络图(无向图)的最短路径。2553北京西安70416952349徐州成都51181234郑州515796512368上海13857广州6实例1运行结果：实例2运行结果：六、总结与心得该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心的各种问题(当然此次试验最终主要解决的问题是：最短路径问题)。这次。9、试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为重要。经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉算法、弗洛伊德算法等，对树的学习有了一个更深的了解。参考文献【1】数据结构严蔚敏.清华大学出版社.【2】数据结构课程设计高大的大炮.极械工业出版社.附录#include#include#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;ty。
10、pedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;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;karcsij=w;printf(有向图的存储结构建立完毕！n);void Dijkstra(MGraph *。
11、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) Dij=Dik+Dkj;pij=pik;void main()MGraph *G;int m,n,e,v,w,k;in。
12、t xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf(*求城市之间最短路径*n);printf(=n);printf(1.求一个城市到所有城市的最短路径n);printf(2.求任意的两个城市之间的最短路径n);printf(=n);printf(请选择 :1或2，选择0退出:n);scanf(%d,&xz);if (xz=2)Floyd(G,n);printf(输入源点(或起点)和终点:v,w:);scanf(%d,%d,&v,&w);k=pvw;if (k=0)printf(顶点%d 到 %d 无路径!n,v,w);elseprintf(从顶点%d 到 %d 最短路径路径是:%d,v,w,v);while (k!=w)printf(-%d,k);k=pkw;printf(-%d,w);printf(径路长度:%dn,Dvw);elseif(xz=1)printf(求单源路径，输入源点v :);scanf(%d,&v);Dijkstra(G,v,n);printf(结束求最短路径，再见!n。