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

数据结构 实验报告五 最短路径实验课程名称 数据结构课程设计 专 业 班 级 学 生 姓 名 学 号 指 导 教 师 2012至 2013学年第 一 学期第 1 至 9 周 目录 一、概述： ..................................................................................................................... 3 1.1 问题描述............................................................................................................... 3 1.2 系统实现的目标.................................................................................................... 3 1.3 系统实现方案 ....................................................................................................... 3 二、系统分析： .............................................................................................................. 4 2.1设计思想................................................................................................................ 4 2.2设计要求................................................................................................................ 4 2.3需求分析................................................................................................................ 4 2.4 算法描述 ............................................................................................................. 5 三、概要设计： .............................................................................................................. 7 3.1 程序流程图 ........................................................................................................... 8 四、详细设计： .............................................................................................................. 9 4.1建立图的存储结构 ................................................................................................. 9 4.2单源最短路径 ........................................................................................................ 9 4.3任意一对顶点间最短路径 .................................................................................... 10 4.4 建立有向图的存储结构....................................................................................... 11 4.5迪杰斯特拉算法................................................................................................... 11 4.6弗洛伊德算法 ...................................................................................................... 12 4.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=1 i++ j=1;j++;jn 修改最短路径和距离 输出结果 5 / 5。