弗洛伊德算法求解最短路径.doc

课课程程设设计计任任务务书书 课程设计名称 数数据据结结构构课课程程设设计计专业 计计算算机机科科学学与与技技术术 物物联联网网方方向向 学生姓名班级学号 题目名称 最短路径求解最短路径求解 起止日期2015年1月5日起至2015年1月16日止 课设内容和要求 内容 给出一张无向图 图上的每个顶点表示一个城市 顶点间的边表示城市 间存在路径 边上的权值表示城市间的距离 试编写程序求解从某一个城市出发到 达任意其他任意城市的最短路径问题 要求 1 能够提供简单友好的用户操作界面 可以输入城市的基本信息 包括城市名称 城市编号等 2 利用矩阵保存城市间的距离 3 利用 Floyd 算法求最短路径 4 独立完成系统的设计 编码和调试 5 5 系统利用 C 语言完成 6 6 按照课程设计规范书写课程设计报告 参考资料 算法与数据结构 C 语言程序设计 教教研研室室审审核核意意见见 教教研研室室主主任任签签字字 指导教师 签名 指导教师 签名 年月日 学学 生 签名 生 签名 年月日 目目 录录 第第 1 章章 概要设计概要设计 1 1 1 题目的内容与要求 1 1 2 总体结构 1 第第 2 章章 详细设计详细设计 2 2 1 主模块 2 2 2 构建城市无向图 3 2 3 添加城市 4 2 4 修改城市距离 5 2 5 求最短路径 6 第第 3 章章 调试分析调试分析 7 3 1 调试初期 7 3 2 调试中期 7 3 3 调试末期 7 第第 4 章章 测试及运行结果测试及运行结果 7 附页 程序清单 附页 程序清单 10 0 第 1 章 概要设计 1 1 题目的内容与要求题目的内容与要求 内容 给出一张无向图 图上的每个顶点表示一个城市 顶点间的边表示城 市间存在路径 边上的权值表示城市间的距离 试编写程序求解从某一个城市出 发到达任意其他任意城市的最短路径问题 要求 1 能够提供简单友好的用户操作界面 可以输入城市的基本信息 包括城市名 称 城市编号等 2 利用矩阵保存城市间的距离 3 利用 Floyd 算法求最短路径 4 独立完成系统的设计 编码和调试 5 系统利用 C 语言完成 6 按照课程设计规范书写课程设计报告 1 2 总体结构总体结构 本程序主要分为四个模块 功能模块见图 1 1 主模块对整个程序起一主 导作用 开始构建一城市无向图 对其进行添加城市顶点 以及对原来的距离数 据进行修改 整体构建结束可以实现求一城市到其他城市的最短路径问题 Floyd 算法求最短 路径 修 改 城 市 距 离 求 最 短 路 径 建 城 市 图 图图 1 1 功能模块图功能模块图 添 加 城 市 顶 点 沈阳航空航天大学课程设计报告 1 第 2 章 详细设计 2 1 主模块主模块 用户根据屏幕上显示的操作提示输入要进行操作的模块 通过调用相对应的 模块程序 达到用户所想进行操作 程序的总框架大致分为四个模块 1 建立城 市无向图 2 添加城市模块 3 修改城市距离 4 求最短路径 具体实现过程见 2 22 2 建立城市无向图 建立城市无向图 2 32 3 添加城市 添加城市 2 42 4 修改城市距离 修改城市距离 2 52 5 求最短路径 流 求最短路径 流 程图程图中通过输入 n 由 n 的值来选择调用相对应子函数 实现所选择的功能 调 用完后可以返回调用主函数进行下一次选择 从而实现反复调用子函数而实现四 个模块的功能等 图图 2 1 主模块流程图主模块流程图 开始 建城市无向图 图 添加城市修改城市距离退出 调用各子函数 Exit 退出程序 结束 输入选择 n 求最短路径 沈阳航空航天大学课程设计报告 2 2 2 构建城市无向图构建城市无向图 根据提示输入城市 对城市无向矩阵图进行初始化 开始 g v m n path 的路径值赋为 2 表示 p 城到 q 城间中间没有可达的路径不经过其他城市 而 g v m n distance 赋值为 0 表示 p 到 p 的距离为 0 流程图流程图中的 MAX 表示的 是最多的城市数量 其值为 20 p q 表示城市的编号 而 path 和 distance 分别表示的路径和城市间距离 g v p q distace 表示 p q 代表的城市间的距 离 图图 2 2 构建城市无向图流程图构建城市无向图流程图 否 是 否 是 开始 p 0 q 0 return g 结束 输入城市 q MAX P MAX g v p q path 2 g v q q distance 0 沈阳航空航天大学课程设计报告 3 2 3 添加城市添加城市 用户根据提示输入想要添加到无向图中的城市 根据屏幕中的提示输入与之 邻接的城市间的距离 然后添加城市距离矩阵图中 同时将 g v m n path 赋值为 1 即表示 p 城到 q 城有路可达且最短路径无需经过其他城市 需注意的是当 g v m n distance 0 表示 p 城到 q 城的距离为 0 当 g v m n distance 99999 则 表示 p 城到 q 城距离无穷大即表示他们之间无路径可达 而当 g v m n distance k 0 k 99999 时表示他们间的距离是 k 流程图中 g n 表示当前图中存储 的城市数量 dis 表示输入的城市间的距离即 q 和 g n 表示城市间的距离 通过 q g n 的条件判断来充分完成图对应的矩阵中的赋值 图图 2 3 添加城市流程图添加城市流程图 否 是 否 是 是 开始 qm 则 d vi vj m 否则为 k 依次类 推 直到所有的 vi 到 vj 的中间城市比较完 最后 d vi vj 的值即为最短距离 同 时在比较的过程中保存路径信息 最后在查询时即可输出路径 具体见第四章 第四章 测试及运行结果测试及运行结果中求最短路径界面 图图 2 4 修改城市距离流程图修改城市距离流程图 否 是 否 是 否 是 是 是 开始 i j k 0 k g n 1 i g n 1 jg v i k di stance g v k j distance g v i j distance g v i k distan ce g v k j distance path k j k i 输入城市求路径 沈阳航空航天大学课程设计报告 6 第 3 章 调试分析 3 13 1 调试初期调试初期 由于编写的程序具有模块化的特性 且 VC 6 0 的调试显然由于 TC 及个 人对 VC 的熟练程度远优于 TC 等方面 我选择先在 VC 6 0 环境下完成除图形化 演示算法过程函数的其他过程 由于数据结构选择的较合理 对 Floyd 算法的理解较为深刻 所以在此环境 下的调试并没有太多困难 3 23 2 调试中期调试中期 在上机输入完程序后 出现了许多错误 其中有一些小错误 比如说忘记写 分号 在这些错误上双击 找到位置 加上分号 还有就是程序中的有的变量在 前面没有定义 只要在前面添加上就可以了 再有就是前后的类型要保持一致 在这块我也犯了个错误 前面是指针类型 后面却是取地址类型 解决办法就是把前面的改成指针类型 保持前后一致 还有就是遗忘分号 逗号 解决方法就是 一步一步的把遗忘的分号 逗号补上 忘记定义变量的类型 比 i 应该是整型的却忘记申明 解决方法就是在函数 内先申明 int 类型的 i 粗心导致很多细节问题 比如该输入英文的括号的 却 输成中文的括号 解决方法 把中英文分开 注意细节问题 3 33 3 调试末期调试末期 输入的数据无法找出正确的路径 解决方法 一步一步的调试 找出问题的 所在 改正逻辑错误 在同学的帮助下 找到了逻辑错误 一步一步地改正 终 于得到预期的结果 第 4 章 测试及运行结果 建图过程 根据屏幕上的显示输入 你会看到如下界面 沈阳航空航天大学课程设计报告 7 添加城市过程 根据界面提示操作 结果如下 添加一城市后如下 沈阳航空航天大学课程设计报告 8 我总共添加了三个城市 最后结果如下界面 求最短路径过程 根据提示我输入了 0 2 号城市编号 结果如下 同理根据提示输入要修改的城市编号 输入后 屏幕上会显示原来的距离 输入 修改后的距离即可修改成功 沈阳航空航天大学课程设计报告 9 附页 程序清单 附页 程序清单 include stdafx h include include include include define MAX 20 城市数量 typedef struct int path int distance Vert typedef struct int n 存放顶点数 char name MAX 60 城市名称及编号 Vert v MAX MAX Mgraph void path Mgraph g int m int n int f int k i a 21 for i 0 i 0 f a f k k g v m k path path g m k f k g v k n path path g k n f for i 1 a i 0 i printf s 到 s 途经 g name m g name n printf s g name a i 沈阳航空航天大学课程设计报告 10 void Floyd Mgraph g int i j k m n h 0 w 0 f 0 s for k 0 k g n 1 k for i 0 i g n 1 i for j 0 jg v i k distance g v k j distance g v i j distance g v i k distance g v k j distance g v j i distance g v i j distance g v i j path k g v j i path g v i j path printf 输入你要查询的两城市编号 n printf 以下是城市相对应的编号 n for i 0 i 0 path g m n f Mgraph Modify Mgraph g 修改俩城市的数据 int p q s printf 输入要修改的两城市编号 n g v p q distance scanf d d printf 原来两城市距离为 d n printf 修改两城市间的距离 n scanf d g v p q distance s 沈阳航空航天大学课程设计报告 11 return g Mgraph ADD Mgraph g 添加新的城市 int p 0 q 0 dis char s printf 请输入添加城市的名字 n scanf s for q 0 q g n q printf s 和 s 是否邻接 是的 1 不是 0 n g name q g name g n scanf d if p 1 邻接信息 g v q g n path 1 printf 请输入 s 和 s 间的距离 n g name q g name g n scanf d g v q g n distance dis g v g n q distance dis else g v q g n distance 99999 99999 表示距离的无限大值 g v g n q distance 99999 99999 表示距离的无限大值 g n return g 添加结束 Mgraph Init Mgraph g 初始化一个邻接矩阵无向图 int q 0 p 0 g n 1 printf 请输入第一个城市的名称 n scanf s g name 0 for q 0 q MAX q for p 0 p MAX p g v p q path 2 g v q q distance 0 return g 初始化结束 沈阳航空航天大学课程设计报告 12 void main int i m 0 Mgraph p do printf n printf 选择操作 n printf 1 创建一个图 n printf 2 添加一个新的城市 n printf 3 修改现有城市的数据 n printf 4 求最短路径 n printf 5 退出程序 n printf n scanf d switch i case 1 p Init p break 初始化 case 2 p ADD p break 添加城市 case 3 p Modify p break 修改城市数据 case 4 Floyd p break 弗洛伊的算法 case 5 exit 0 break 退出程序 printf 是否继续 1 继续 0 退出 n scanf d system cls while m 1 沈阳航空航天大学课程设计报告 13 课程设计总结 课程设计总结 开始拿到题后感觉很难 没有一点思绪 就借了一些数据结构与 C 语言设 计方面的书看了一些才慢慢有点思路 于是就尝试开始编程序 在写程序的过程中总是会查课本去注意一些细节方面的问题 也让我懂得 了即使是再小再细的东西在学习的过程中也要重视 深深体会