青岛理工大学琴岛学院 设 计 报 告 课题名称：数据结构课程设计 学 院：计算机工程系 专业班级：计算机网络技术 学 号：aaaaaa 学 生： aaa 指导教师： aaaaaaa 青岛理工大学琴岛学院教务处 2011 年 12 月 18 日 学 生 Aaa 指导教师 aaa 课题名称 求解最优交通路径 设计时间 2011/12/12-2011/12/18 设计地点 分散实习 设计目的 1．利用C/C++编写一个程序，实现对全国的交通图进行最短路径及其距离的查询 2.熟悉运用迪克斯塔拉算法解决实际问题。 设计内容（包括设计过程、主要收获、存在问题、解决措施、建议，不少于 2000 字） 一、 运行环境 Microsoft Visu al C++6.0 不仅仅是一个编译器。它是一个全面的应用程序开发环境。 二、系统流程图 开始 CreatUDN()创建界面 ShortestPath( )计算出最短路径及距离Ou tpu t()输出起点和终点以及中间的点 输出最短路径及距离 结束 输入要查询的两个城市编号 m_v 0,m_v 1 进入查询界面 是 否 继 续 查询选择 查看各城市对应的编号 判断前后两次输入的编号是否在查询范围输入要查询的两个城市编号 输出两站点路径及最短距离 退出 否 是 Y N 三 、 函 数 及 变 量 说 明 相 关 函 数 （ 一 ）（ 1） 首 先 创 建 CreatUDN( )函 数 生 成 一 个 拥 有 25 个 城 市 ， 30 条 公 路 的 交 通 图 ， 并 录 入 两城 市 之 间 的 权 值 即 距 离 ， 其 中 顶 点 对 应 于 城 市 ， 边 对 应 于 城 市 间 直 接 通 路 ， 根 据 实 际 问 题 ， 在生 成 的 交 通 图 中 所 有 的 通 路 都 是 双 向 的 ，即 如 果 A 城 市 到 B 城 市 有 直 接 通 路 ， 且 里 程 为 k 千 米 ，则 B 城 市 到 A 城 市 也 有 直 接 通 路 ， 并 且 里 程 同 样 为 k 千 米 。 创 建 对 话 框 提 示 用 户 输 入 发 出 城 市和 终 到 城 市 的 序 号 ， 再 调 用 ShortestPath( )函 数 求 出 最 短 路 径 ， 由 Output( )函 数 输 出 结 果 。 （ 2） ShortestPath( )利 用 了 数 据 结 构 中 图 论 中 的 最 短 路 径 相 关 的 弗 洛 伊 德 算 法 。 Output()函数 把 计 算 的 结 果 格 式 化 输 出 ...
