《数据结构课程设计》最短路径问题实验报告.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.23M 资料格式：doc 举报版权申诉

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第1页.png

第1页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第2页.png

第2页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第3页.png

第3页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第4页.png

第4页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第5页.png

第5页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第6页.png

第6页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第7页.png

第7页 / 共16页

gejiantaomaruli-5155977-16359647283732501261.doc.pdf-第8页.png

第8页 / 共16页

一、概述

二、系统分析

三、概要设计

四、详细设计

4.1建立图的存储结构

4.2单源最短路径

4.3任意一对顶点之间的最短路径

五、运行与测试

参考文献

附录

目录一、概述 .......................................... 1 二、系统分析 ...................................... 1 三、概要设计 ...................................... 2 四、详细设计 ...................................... 5 4.1 建立图的存储结构 ............................ 5 4.2 单源最短路径 ................................ 6 4.3 任意一对顶点之间的最短路径 .................. 7 五、运行与测试 .................................... 8 参考文献 ......................................... 11 附录 ............................................. 12

交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从 A 城到 B 城途中中转次数最少；如何选择一条路径使得从 A 城到 B 城里程最短；如何选择一条路径使得从 A 城到 B 城花费最低等等的一系列问题。二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 1

三、概要设计可以将该系统大致分为三个部分： 1 建立交通网络图的存储结构； 2 解决单源最短路径问题； 3 实现两个城市顶点之间的最短路径问题。交通咨询系统迪杰斯特拉算法（单源最短路径）建立图的存储结构义迪杰斯特拉算法流图：费洛依德算法（任意顶点对间最短路径） 2

弗洛伊德算法流图： 3

四、详细设计 4.1 建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设 G=(V,E)是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下定义的 n 阶方阵。 ],[ j iA  ijW     0 或  ，若 (V i )V, j 或  V,V i j  E(G)  ，其他情况注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有 n 个元素的一维数组来存储顶点信息（下标为 i 的元素存储顶点 iV 的信息）。邻接矩阵的存储结构： #define MVNum 100 //最大顶点数 typedef struct { VertexType vexs[MVNum];//顶点数组，类型假定为 char 型 Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，假定为 int 型 }MGraph; 注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。 5

4.2 单源最短路径单源最短路径问题：已知有向图(带权)，期望找出从某个源点 S ∈V 到 G 中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图 G=(V,E)，其中 V={1,2，……n}，cost 是表示 G 的邻接矩阵， cost[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 之间的最短路径的前驱顶点。 6

4.3 任意一对顶点之间的最短路径任意顶点对之间的最短路径问题，是对于给定的有向网络图 G=(V,E),要对 G 中任意一对顶点有序对，“V,W(V≠W)”，找出 V 到 W 的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法 n 次，即可求得每对之间的最短路径。费洛伊德算法的基本思想：假设求从 Vi 到 Vj 的最短路径。如果存在一条长度为 arcs[i][j]的路径，该路径不一定是最短路径，还需要进行 n 次试探。首先考虑路径和是否存在。如果存在，则比较路径和的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于 1 的最短路径。其次，考虑从 vi 到 vj 是否包含有顶点 v2 为中间顶点的路径< vi,…,v2,…,vj>，若没有，则说明从 vi 到 vj 的当前最短路径就是前一步求出的；若有，那么可分解为和，而这两条路径是前一次找到的中间点序号不大于 1 的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求得的从 vi 到 vj 的中间顶点序号不大于 1 的最短路径比较，取其长度较短者作为当前求得的从 vi 到 vj 的中间顶点序号不大于 2 的最短路径。依此类推……直至顶点 vn 加入当前从 vi 到 vj 的最短路径后，选出从 vi 到 vj 的中间顶点序号不大于 n 的最短路径为止。由于图 G 中顶点序号不大于 n，所以 vi 到 vj 的中间顶点序号不大于 n 的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是 vi 到 vj 的最短 7

分享到：

赞收藏

资料库

《数据结构课程设计》最短路径问题实验报告.doc

相关推荐

课程资源

热门标签

最新资料