单元点最短路径算法的实现 课程设计.doc

数据结构课程设计 设计说明书 单元点最短路径算法的实现单元点最短路径算法的实现 学生姓名 学 号 班 级 成 绩 指导教师 余冬梅 数学与计算机科学学院 2014 年 3 月 7 日 课程设计任务书 2013 2014 学年第学年第 2 学期学期 专业 学号 姓名 课程设计名称 数据结构课程设计 设计题目 单源点最短路径算法的实现 完成期限 自 2014 年 2 月 24 日至 2014 年 3 月 7 日共 2 周 设计依据 要求及主要内容 可另加附页 最短路径问题是数据结构中数组部分的重点和难点知识 它属于图结构问题 其解决方法也有不 少 如 Dijkstra A star 可自行选择算法 本课程设计按以下的要求运用 C C 结构体 指针 数据结构等基知识编程实现 任务要求 任务要求 1 阐述设计思想 画出流程图 2 任意建立存储 m 个顶点 n 条边的图 3 按照用户要求的 源点和目标点 求出它们间的最短路径 并打印出路径 若无路径需给出说明 4 说明测试方法 写 出完整的运行结果 较好的界面设计 5 按照格式要求完成课程设计说明书 设计要求设计要求 1 问题分析和任务定义 根据设计题目的要求 充分地分析和理解问题 明确问题要求做什么 而不是怎么做 限制条件是什么 确定问题的输入数据集合 2 逻辑设计 对问题描述中涉及的操作对象定义相应的数据类型 并按照以数据结构为中心的原 则划分模块 定义主程序模块和各抽象数据类型 逻辑设计的结果应写出每个抽象数据类型的定义 包括数据结构的描述和每个基本操作的功能说明 各个主要模块的算法 并画出模块之间的调用关 系图 3 详细设计 定义相应的存储结构并写出各函数的伪码算法 在这个过程中 要综合考虑系统功 能 使得系统结构清晰 合理 简单和易于调试 抽象数据类型的实现尽可能做到数据封装 基本操 作的规格说明尽可能明确具体 详细设计的结果是对数据结构和基本操作做出进一步的求精 写出数 据存储结构的类型定义 写出函数形式的算法框架 4 程序编码 把详细设计的结果进一步求精为程序设计语言程序 同时加入一些注解和断言 使 程序中逻辑概念清楚 5 程序调试与测试 能够熟练掌握调试工具的各种功能 设计测试数据确保程序正确 调试正确 后 认真整理源程序及其注释 形成格式和风格良好的源程序清单和结果 6 结果分析 程序运行结果包括合法的输入及其输出结果和含有非法的输入及其输出结果 算法 的时间 空间复杂性分析 7 编写课程设计报告 以上要求中前三个阶段的任务完成后 先将设计说明书的草稿交指导老师面审 审查合格后方可 进入后续阶段的工作 设计工作结束后 经指导老师验收合格后将设计说明书打印装订 指导教师 签字 教研室主任 签字 批准日期 2014 年 2 月 23 日 课程设计评阅 评语 指导教师签名 年 月 日 指导教师 余冬梅 教研室负责人 申静 摘摘 要要 本系统以 VC 作为软件开发环境 C 语言作为程序开发语言 邻接矩阵作为存储结构 设计与 实现了最短路径运算 该系统实现了有向图的存储 最短路径的运算等主要功能 依照该系统可以解 决生活中许多问题 比如交通路线的选择 工程时间的预算等等 让人们可以做出合理的选择 本系 统通过分析课题的背景 意义 要求 分别从课题描述 逻辑设计 算法设计 调试与测试等各个方 面详细介绍了系统的设计与实现过程 最后对系统的完成情况进行了总结 界面清晰 操作简单 易 于用户接受 关键词关键词 VC 邻接矩阵 最短路径 目录目录 1 课题描述 1 2 问题分析与任务定义 2 2 1 问题分析 2 2 2 任务定义 2 3 算法设计 3 3 1 图的邻接矩阵的存储结构 3 3 2 DIJKSTRA算法思想 4 4 系统逻辑设计 5 4 1 主函数流程图如图 4 1 所示 5 4 2 CREATE函数流程图如图 4 2 所示 6 4 3 DIJKSTRA函数流程图如图 4 3 所示 8 4 源代码 11 5 调试与测试 14 6 总结 16 参考文献 17 0 1 1 课题描述课题描述 乘车旅行的人大多数都希望找出到目的地尽可能短 花费少的行程 那么如何找出从 出发点到目的地的最短路径 由于路径比较多 所以用手工计算起来比较复杂 抽象 因 此人们用计算机语言代替手工计算来求得最短路径 而在计算机语言中迪杰斯拉算法比较 常用 简捷 故人们经常借助计算机程序用迪杰斯拉算法求得单源点的最短路径 这样可 以广泛的提高效率 而且条理清晰 通俗易懂 1 2 2 问题分析与任务定义问题分析与任务定义 2 1 问题分析 本系统是要解决的是单源点最短路径问题 设计程序 实现最短路径的求法 系 统需要达到的主要功能如下 1 编写算法能够建立带权图 并能够用 Dijkstra 算法求该图的最短路径 2 能够选择图上的任意一顶点做为开始节点 最短路径输出不必采用图形方式 可顶点序列方式输出 3 根据课设题目要求 拟将整体程序分为三大模块 两个子模块相互独立 没 有嵌套调用的情况 在主模块中调用上面两个子模块 2 2 任务定义 根据课设题目要求 拟将整体程序分为三大模块 两个子模块相互独立 没有嵌 套调用的情况 在主模块中调用上面两个子模块以下是三个模块的大体分析 1 建立有向图的存储结构 2 应用 Dijkstra 算法求出该有向图的最短路径 3 在主函数中调用两个子函数 完成最短路径的程序设 2 3 3 算法设计算法设计 3 1 图的邻接矩阵的存储结构 一个图的邻接矩阵表示唯一的 故在图的邻接矩阵表示中 除了需要用一个二维 数组存储顶点之间相邻关系的邻接矩阵外 通常还需要使用一个具有 n 个元素的一维 数组存储顶点信息 其中下标为 i 的元素存储顶点 vi 的信息 本设计是基于类 C 语言 的算法描述 因此 图的邻接矩阵的存储结构定义如下 define MVNum 50 typedef struct VertexType vexs MVNum Adjmatrix arcs MVNum MVNum Mgraph 在本系统中 以邻接矩阵存储有向图 如图 3 1a 中有向图 G 所示 其邻接矩阵 为图 3 1b 所示 20 1010 505 f ea b c d 100 60 30 图 3 1a 有向图 G 10 30 100 5 50 10 20 60 b a e f 5 50 图 3 1a 有向图 G 图 3 1b G 的邻接矩阵 10 30 100 5 50 10 20 60 图 3 1b G 的邻接矩阵 图 3 1b G 的邻接矩阵 3 3 2 Dijkstra 算法思想 1 Dijkstra 算法核心是贪心 实质是按路径长度递增产生诸顶点的最短路径算 法 用自然语言描述如下 初始化 S 和 D 置空最短路 径终点集 置初始的最短路径值 S v1 TRUE D v1 0 While S 集中的顶点数 n 开始循环 每次求的 v1 到某个 v 顶点的最短路径 并将 v 加到 S 集中 S v TRUE 更新当前最短路径及距离 2 Dijkstra 算法结束后 通过设置一个数组记录下一个节点的前趋节点 然后 通过倒叙的方式输出该最短路径 4 4 4 系统逻辑设计系统逻辑设计 4 1 主函数流程图如图 4 1 所示 3 1 主函数流程图 4 2 Create 函数流程图 开始 输入数据 调用 Create 函数 调用 Dijkstra 函数 k 1 开始 输入顶点个数和边数 m n 调用 Create 函数 建立图的邻接矩阵 请输入初始点 v 调用 Dijkstra 函数 求得最短路径 结束 图 4 1 主函数流程图 Y N 5 4 2 Create 函数流程图如图 4 2 所示 开始 定义顶点序号 i 1 顶点数 m 边 数 n i m Y 存入一维向量 G vexs i i i i 1 N i 1 i m Y j 1 jarcs i j w 变量 k 1 k n 给邻接矩阵有关单元赋权值 w G arcs i j w k k 1 结束 图 4 2 Create 函数流程图 Y N 定位 i j i a a 1 j b a 1 接上一页 7 4 3 Dijkstra 函数流程图如图 4 3 所示 开始 定义 G 中 v1 到其余顶点 v 的最短路径 带权长度 及最短路径终点的集合 int D MVNum P MVNum boolean S MVNum 定义顶点数 int m v 1 v m Y 置空 S S v FALSE D v G arcs v1 v 若权值小于最大值 无穷 D v Maxint Y P v v1 v v 1 P v 0 N 初始化 v1 顶点属于 s 集 D v1 0 S v1 TRUE 开始主循环 每次求得 v1 到某个 v 顶点的最短路径 并加 v 到 s 集 i 2 N 接下一页 8 S v TRUE i m mm m 当前所知离 v1 顶点的最近距离 min Maxint 顶点变量 w 1 w m Y v w W 顶点离 v1 更近 min D w S v TRUE w w 1 Y w 1 w m 修改 D w P w D w D v G arcs v w P w v w w 1 i i 1 Y N N Y N 接上一页 S w 定义顶点 typedef int Adjmatrix typedef enum FALSE TRUE boolean typedef struct 图的邻接矩阵 VertexType vexs MVNum 顶点向量 存放顶点的一维数组 Adjmatrix arcs MVNum MVNum 邻接矩阵二维数组 MGraph 定义邻接矩阵结构类型 void CreateMGraph MGraph G int m int n 采用数组 邻接矩阵 表示法 构造图 G int i j k w char a b for i 1 ivexs i i for i 1 i m i 初始化邻接矩阵 for j 1 jarcs i j Maxint printf 输入 d 条边的 i j 及 w n n for k 1 karcs i j w 弧的权值 printf 有向图的存储结构建立完成 n printf n void Dijkstra MGraph G int v1 int m 用 Dijkstra 算法求 G 中 v1 顶点到其余顶点 v 的最短路径 p v 及带权长度 D v 11 int D MVNum P MVNum int v i w min boolean S MVNum S 以求得最短路径的终点的集合 for v 1 v m v S v FALSE D v G arcs v1 v if D v Maxint P v v1 else P v 0 D v1 0 S v1 TRUE 初始化 v1 顶点属于 s 集 开始主循环 每次求得 v1 到某个 v 顶点的最短路径 并加 v 到 s 集 for i 2 i m i 其余 n 1 个顶点 min Maxint 当前所知离 v1 顶点的最近距离 for w 1 w m w if S w min D w w 顶点离 v1 顶点更近 S v TRUE for w 1 w m w 更新当前最短路径及距离 if S w P w v printf 路径长度 路径 n for i 1 i m i printf 5d D i printf 12c i 1 a v P i while v 0 12 printf c v 1 a v P v printf n void main MGraph G int m n v char ch printf 输入所需图的顶点个数和边数 m n scanf d d CreateMGraph while v m printf 求最短路径 请输入初始点 v fflush stdin scanf c printf n v ch a 1 Dijkstra G v m 13 5 5 调试与测试调试与测试 1 合法数据测试结果如图 5 1 所示 图 5 1 合法数据测试结果 14 2 非法数据测试结果如图 5 2 所示 图 5 2 非法数据测试结果 当前任务已达到任务目标 对于 n 个顶点的有向图 求一个顶点到其他顶点的最短路 径的时间为 O n 调整最短路径的循环共执行 n 1 次 所以 时间复杂度是 O n2 采用 邻接矩阵存储有向图 应处理每两个顶点之间的关系 所以空间复杂度为 O n2 15 6 6 总结总结 本次课程设计涉及到的范围很广 让我比较系统的对 C 语言和数据结构知识进行了一 次整理和复习 本系统存在的问题主要是程序完成后 调试时没有发现问题 但是当输入 开始节点后 运行框却不停的出现 a 后来重新检查程序时发现 for 循环的括号后面 多了一个 去掉该分号之后 程序可以运行 在这次课程设计中我体会到 C 语言超强 的逻辑性以及能够熟练使用 VC 编译环境的重要性 对 C 语言与数据结构这两门课程有了 新的认识 它们既有联系 又相互区别 在编写程序过程中要灵活应用 我对数据结构的 理解还有待加强 这次课程设计应用的算法是 Dijkstra 算法 在学习的过程中自己对这方 面的知识比较生疏 所以在算法设计过程中比较困难 尤其是设计 Dijkstra 算法的流程图