数据结构实验报告五最短路径

1、实验课程名称数据结构课程设计专科班学生名称学号指导教师2012-2013学年第一学期1-9周目录一、概述：21.1问题说明21.2系统实现的目标21.3系统实施方案2二、系统分析：32.1设计理念32.2设计要求32.3需求分析32.4算法说明4三、大纲设计：63.1程序流程图7四、详细设计：84.1图中的存储结构设置84.2单一来源最短路径84.3顶点对之间的最短路径94.4构造有向图的存储结构104.5第纳尔算法104.6弗洛伊德算法114.7运行主节目12五、操作和测试：13六：总结和经验15附录：节目代码15一、概述：1.1问题说明交通网络牙齿很发达，交通工具和交通方式牙齿不断更新的今

2、天，人们出差、旅行或其他旅行时，不仅节约交通费用，还对里程和必要的时间等感兴趣的牙齿。对于这些人关心的问题，可以使用图片结构表示交通网络系统，使用计算机构建交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。牙齿交通系统可以回答旅客提出的各种路径选择问题。例如，问题之一是：“从a点到b点的旅客想选择途中中转次数最少的路线。”假设图中的每个站都要换车，牙齿问题是找到从顶点a到顶点b包含的边数最小的路径。我们只需从顶点a开始，广度优先搜索作画。一旦遇到顶点b就终止。(阿尔伯特爱因斯坦，northern exposure(美国电视电视剧)，作品)结果，从树、根顶点a老师到顶点b的路径是最少的

3、传输路径。路径中a和b之间的顶点是路径的中继点，但只是最简单图形的最短路径问题。系统还可以回答这样的路径选择问题。1.2系统实现的目标通过课程设计，了解和初步了解实现设计、大型系统的整个过程，包括系统分析、编码设计、系统集成、调试分析、数据结构选择、设计、实施和操作方法的掌握，为进一步的应用程序开发奠定了基础。应用所学的数据结构知识，独立完成问题分析，结合数据结构理论知识编写解决指定问题的程序。1.3系统实施方案首先，决定系统要达到什么目的，为了达到这种目的，首先要实现的程序。这是关键部分。划分模块、源代码、牙齿程序大致分为6个模块，由主函数组和5个自定义函数组组成。然后进行机器调试，协调几个

4、大模块，组成完全实现其功能的程序，最后提交设计报告。二、系统分析：2.1设计理念利用邻接矩阵存储与交通网络地图的信息，利用迪塞斯特拉算法实现地图单一来源最短路问题，然后利用斐洛算法实现图片中任何一对顶点之间的最短路问题，从而实现旅客需要咨询的问题。2.2设计要求牙齿交通咨询系统必须完成城市网络地图的存储，实现从任意城市顶点到其他城市顶点的最短路径问题，还必须实现两个城市顶点之间的最短路径问题。因此，设计必须分为三个部分。一是构建交通网络地图的存储结构。二是解决单一源路径问题。最后实现两个城市之间的最短路径问题。设计要求：1.构建交通网络网络的存储结构。整体设计需要绘制流程图。3.供应商程序测试

5、节目。4.界面很熟悉。2.3需求分析根据需要，在系统中创建无向图。系统必须灵活，用户可以根据当前交通网络图输入和更改初始数据。系统基于用户的输入构建了无向图的结构，通过dickstra算法和弗洛伊德算法实现了需求，并提供了两种茄子功能供用户选择。2.4算法说明输入城市和公路数据查询从一个城市到另一个城市的最短路径基于无向图生成查询功能结构建设教父相通网络交通祖怀系统字典城市之间的距离查询两个城市之间的最短路径迪克斯特拉算法特定流程图开始初始化距离和路径i=1j=1；j；jn弗洛伊德算法特定流程图开始初始化距离和路径从到的最短路径长度，其中只有集中的节点设置为中间节点输出结果最短路径通过点k最短

6、路径不通过点k三、大纲设计：程序包含两种茄子抽象数据类型。一个是图形，另一个是队列。1、设置“图片”抽象数据类型定义。adt graph数据对象v: v是具有相同属性(称为顶点集)的数据元素的集合。数据关系r:r=vrvr=v，w | v，w-vp(v，w)，v，w表示从v到w的圆弧。谓词p(v，w)定义了圆弧v，w的含义或信息。默认操作p:creategraph(g，v，vr)；初始条件：v是图形的顶点集，vr是图形中弧的集合。任务结果：按照v和vr定义构建图表。locatevex(g，u):初始条件：图g存在，u和g的顶点具有相同的特征。操作结果：如果g具有顶点u，则地物返回该顶点的位置。

7、否则，将返回其他信息。first_next_adj(g，v)；初始条件：图g存在，v是g的顶点。操作结果：返回v的第一个相邻顶点。如果g没有相邻顶点，则返回null。dfstraverse(g，i):初始条件：图g存在，i是邻接矩阵中顶点的位置。作业结果：从i开始，先遍历图形的深度。bfstraverse(g，i):初始条件：图g存在，i是邻接矩阵中顶点的位置。作业结果：从i开始，先遍历图片的宽度。 adtgraph2、设置队列的抽象数据类型定义。adt queue数据对象：d= a i a i数据关系：r1=a i，a i1 | a i1，a id，i=2，n规则a1结尾是队列标头，a n结

8、尾是队列结尾。基本任务：initqueue(q)任务结果：配置空队列q。enqueue(q，e)初始条件：队列q已存在。任务结果：插入元素e为q的新团队尾部元素dequeue(q)初始条件：队列q已存在。任务结果：删除q的相对元素并返回值。queueempty(q)初始条件：队列q已存在。任务结果：如果q为空队列，则返回1，否则返回0。queuelenghth(q)初始条件：队列q已存在。操作结果：返回q的元素数，即队列长度。gethead(q，e)初始条件：q是非空队列。工作结果：使用e返回q的对手元素。 adt queue3、牙齿程序包含三个茄子模块。1)主节目模块void main()选

9、择要创建的图表的类型。请创建图表并以邻接矩阵格式打印。找到地物的深度和广度优先搜索以及顶点的第一个相邻点。查找从一个源点到其馀顶点的最短路径。2)图形模块实现图的抽象数据类型和基本操作3)队列模块实现队列的抽象数据类型和当前操作3.1程序流程图四、详细设计：设置4.1图形的存储结构首先定义交通地图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。g=(v，e)是具有n个顶点的图形，g的邻接矩阵是n阶方阵，定义如下：ai，j=邻接矩阵列标头，当栏标头顺序一致时，插图的邻接矩阵表现法是唯一的。根据图的邻接矩阵表示，除了将顶点之间的相邻关系存储为二维阵列的邻接矩阵外，通常还需要使用n个元素一维

10、阵列存储顶点信息。其中下标是i的元素存储顶点i的信息。因此，图的邻接矩阵存储结构定义如下：#definf mvnum 88 /最大顶点数typedef structvertex type vexsmv num；/vertex阵列，假设为char类型adj matrix arcsmv nummv num；/邻接矩阵，假设为int类型 mgraph4.2单一来源最短路径对最短路径的提法很多。这里首先介绍单个源最短路问题，即乳香度(卷权)。我想查找从源点sv到g其馀顶点的最短路径。为了便于叙述，我们将路径的起点称为源点，路径的最后一个顶点称为终点。(约翰肯尼迪，美国电视电视剧)那么，如何得到给定方向

11、性图的单个源最短路径呢？dijkstra提出了随着路径长度增加点的最短路径算法，即dijkstra算法。dijestra算法追求最短路径实现。g=(v，e)是直接图形，节点集，cost是表示g的邻接矩阵，costij表示转向权。如果没有方向边，则costij的权重为无穷大，此处为32767。s是每个元素代表一个顶点的集合，从源到牙齿顶点的最短距离已经被求出。将顶点v1设置为源点，并且集合s的初始状态仅包含一个元素，顶点v1。阵列dist记录从源点到其他顶点的当前最短距离。初始值为dist i=cost v1 i，i=1，2，n。在非s顶点集v-s中，选择顶点w以最小化distw的值。因此，仅通

12、过源点到w之间s的顶点，向集合s添加w，并调整dist中记录的源点到v-s中每个顶点v的距离。在原始distv和distw costwv中，选择较小的值作为新dist。重复以上过程，直到v-s为空。结果s记录从源点到其顶点的最短路径的顶点集合，阵列dist记录从源点到v中其馀顶点的最短路径，path是最短路径的路径阵列。其中pathi表示从源点到顶点i的最短路径上的前导顶点。因此，dijestra算法可用的自然语言如下：初始化s和d，清空最短路径端点集，并设置初始最短路径值。sv1=true；dv1=0；/s集最初仅包含源点，从源点到源点的距离为零。while (s集中的顶点数及其是否存在)。

13、如果有，比较和vi，v1，vj的路径长度，长度短是当前求的最短路径。牙齿路径是中间顶点序列号不大于1的最短路径。其次，考虑从vi到vj是否包含顶点v2为中间顶点的路径。否则，从vi到vj的当前最短路径是在前面的步骤中获得的。如果存在，可以使用和分割。牙齿两条路径是以前找到的中间顶点序列号不大于1的最短路径，加上两条路径长度即可得出路径长度。将牙齿长度与从vi到vj的中间顶点编号不大于1的最短路径进行比较，使用较短的当前vi到vj的中间顶点编号不大于2的最短路径。以这种方式添加顶点vn牙齿从当前vi到vj的最短路径，然后选择从vi到vj的中间顶点编号不大于n的最短路径。图g中的顶点编号不大于n，因此从vi到vj的中间顶点编号不大于n的最短路径，并且考虑到所有顶点都可能是中间顶点，因此是从vi到vj的最短路径。4.4构造有向图的存储结构void createmgraph (mgraph * g，int n，int e)int i、j、k、w；for(i=1)；i=n；i)g-vexsi=(char)i；for(i=1)；i=n；i)for(j=1)；j=n；j)g-arcsij=max int；printf(输