文档介绍：该【《数据结构课程设计》最短路径问题实验报告 】是由【文艺人生】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【《数据结构课程设计》最短路径问题实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。《数据结构课程设计》最短路径问题实验报告目录一、概述 0二、系统分析 0三、概要设计 1四、详细设计 7五、运行与测试 8参考文献 11附录 1200三、概要设计可以将该系统大致分为三个部分:建立交通网络图的存储结构;解决单源最短路径问题;实现两个城市顶点之间的最短路径问题。交通咨询系统迪杰斯特拉算法(单源最短路径)费洛依德算法(任意顶点对间最短路径)建立图的存储结构义0迪杰斯特拉算法流图:1弗洛伊德算法流图:23四、。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下定义的n阶方阵。注:一个图的邻接矩阵表示是唯一的!其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息(下标为i的元素存储顶点的信息)。邻接矩阵的存储结构:#defineMVNum100//最大顶点数typedefstruct{VertexTypevexs[MVNum];//顶点数组,类型假定为char型Adjmatrixarcs[MVNum][MVNum];//邻接矩阵,假定为int型}MGraph;注:由于有向图的邻接矩阵是不对称的,故程序运行时只需要输入所有有向边及其权值即可。:已知有向图(带权),期望找出从某个源点S∈V到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想:设有向图G=(V,E),其中V={1,2,……n},cost是表示G的邻接矩阵,cost[i][j]表示有向边<i,j>的权。若不存在有向边<i,j>,则cost[i][j]的权为无穷大(这里取值为32767)。设S是一个集合,集合中一个元素表示一个顶点,从源点到这些顶点的最短距离已经求出。设顶点V1为源点,集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离,其初值为dist[i]=cost[i][j],i=2,……n。从S之外的顶点集合V-S中选出一个顶点w,使dist[w]的值最小。于是从源点到达w只通过S中的顶点,把w加入集合S中,调整dist中记录的从源点到V-S中每个顶点v的距离:从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程,直到S中包含V中其余顶点的最短路径。最终结果是:S记录了从源点到该顶点存在最短路径的顶点集合,数组dist记录了从源点到V中其余各顶点之间的最短路径,path是最短路径的路径数组,其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。5