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

实验课程名称数据结构课程设计专业班级学生姓名学号指导教师2012至2013学年第一学期第1至9周目录一、概述：...............................................................................................................................31.1问题描述........................................................................................................................31.2系统实现的目标............................................................................................................31.3系统实现方案................................................................................................................3二、系统分析：.......................................................................................................................42.1设计思想.........................................................................................................................42.2设计要求.........................................................................................................................42.3需求分析.........................................................................................................................42.4算法描述......................................................................................................................5三、概要设计：.......................................................................................................................73.1程序流程图....................................................................................................................8四、详细设计：.......................................................................................................................94.1建立图的存储结构.........................................................................................................94.2单源最短路径.................................................................................................................94.3任意一对顶点间最短路径...........................................................................................104.4建立有向图的存储结构..............................................................................................114.5迪杰斯特拉算法...........................................................................................................114.6弗洛伊德算法...............................................................................................................124.7运行主控程序..............................................................................................................13五、运行与测试：.................................................................................................................14六、：总结与心得.................................................................................................................16附录：程序代码.................................................................................................................16一、概述：1.1问题描述在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。1.2系统实现的目标通过进行课程设计，了解并初步掌握设计、实现较大系统的完整过程，包括：系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。1.3系统实现方案首先确定系统要实现怎样的目的，实现这些目的需要先实现哪些程序，这就是核心部分，划分出模块并写出其源代码，此程序大致分了六大模块，由一个主函数组和五个自定义函数组成，而后是上机调试，将几大模块组成一个协调完整的能实现其功能的程序，最后提交设计报告二、系统分析：2.1设计思想用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。2.2设计要求该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。设计要求：1.建立交通网络网的存储结构。2.总体设计要画流程图。3.提供程序测试方案。4.界面友好。2.3需求分析根据要求，需要在系统中建立无向图。系统应该有高度灵活性，可以由用户根据当前交通网络图输入初始数据，并且可以更改。系统根据用户的输入建立无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功能供用户选择。2.4算法描述狄克斯特拉算法的具体流程图交通查询系统录入城市及道路数据预置城市间的距离构建交通网根据无向图建立查询功能查询一个城市到其它城市的最短路径查询任意两城市间的最短路径开始初始化距离和路径i=1j=1;j++;jn修改最短路径和距离输出结果i++in弗洛伊德算法的具体流程图开始初始化距离和路径设为从到的只以集合中的节点为中间节点的最短路径的长度输出结果最短路径经过点k最短路径不经过点k三、概要设计：程序中将涉及下列两个抽象数据类型：一个是图，一个是队列。1、设定“图”的抽象数据类型定义：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合,称为顶点集。数据关系R：R={VR}VR={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，则返回该顶点在图中位置；否则返回其他信息。First_next_adj（G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：返回V的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。DFSTraverse(G,i);初始条件：图G存在，i为某个顶点在邻接矩阵中的位置。操作结果：以i为起始点，对图进行深度优先遍历。BFSTraverse(G,i);初始条件：图G存在，i为某个顶点在邻接矩阵中的位置。操作结果：以i为起始点，对图进行广度优先遍历。｝ADTGraph2、设定队列的抽象数据类型定义：ADTQueue{数据对象：D={aiai∈BiTree,i∈N+}数据关系：R1={ai,ai−1|ai−1,ai∈D,i=2,…，n}约定a1端为队列头，an端为队列尾。基本操作：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的对头元素。}ADTQueue3、本程序包含三个模块1）主程序模块voidmain(){选择欲建图的类型；构建图并对其用邻接矩阵的形式打印；对图进行深度和广度优先搜索以及求某个顶点的第一邻接点