《算法课程设计-利用迪杰斯特拉算法实现无向图的最短路径的计算和求解》由会员分享，可在线阅读，更多相关《算法课程设计-利用迪杰斯特拉算法实现无向图的最短路径的计算和求解（27页珍藏版）》请在金锄头文库上搜索。
1、算法课程设计算法课程设计- -利用迪杰斯特拉算法实现无向图的最短利用迪杰斯特拉算法实现无向图的最短路径的计算和求解路径的计算和求解摘要本次课程设计主要核心为利用迪杰斯特拉算法实现无向图的最短路径的计算和求解。要求理解迪杰斯特拉算法的具体实现流程、学会正确使用该算法求解实际问题。本次课程设计具体内容是：为自己学校建立一个校园导航系统。该系统应该具有：查询任意两点最短路径以及查询任意一点到其他各点的最短路径。本程序要求结合最短路径迪杰斯特拉算法以及相应的数据结构的定义和使用，实现一个最短路径算法的简单应用。本文主要包括的函数模块有：数据结构定义、无向图的建立、导航图建立、最短路径求解及主函数模块。
2、还有运行调试过程的截图，最后附上程序清单，以供查阅。本课程设计是对书本知识的简单应用，以此培养大家用书本知识解决实际问题培养实际工作所需要的动手能力以科学理论和工程上的技术，规范地开发大型、复杂、高质量的应用软件和系统软件目 录摘要 I1 问题描述 12 方案设计 22.1 数据结构定义模块22.2 功能模块定义22.2.1 无向图构造模块22.2.2 导航图建立模块22.2.3 求最短路径模块32.2.4 主菜单 33 流程图43.1 系统运行流程图 43.2 迪杰斯特拉算法流程图 54 功能模块代码实现 64.1 创建无向图函数 64.2导航菜单生成74.3最短路径求解函数85 运行调试1
3、15.1查询系统导航界面115.2两点最短距离导航115.3某点到其他所有点最短距离125.4退出系统 126 程序设计总结137 参考文献14附录 程序清单15问题描述这是一个最短路径算法的简单应用，体现了理论与实际的结合。在完成本系统过程中，应用所学知识解决具体的实际问题。根据本设计要求，首先应该根据本学校的具体实际，建立校园平面图。然后根据该图建立无向图的邻接矩阵，矩阵的值表示两点之间的实际距离。最后根据用户请求调用迪杰斯特拉算法，并输出相应的路径信息。该系统还应该设计可视化导航键面，方便用户使用。根据本课程设计要求，本系统应该具备如下功能：1、查询任意两点间的最短路径（包括途经地点以及
4、最短距离） ；2、查询任意一点到其他各点的最短路径（包括途经地点以及最短距离） ；3、能完成连续的查询工作；4、用户查询完后能方便的退出程序系统。方案设计2.1 数据结构定义模块本模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩阵的存储结构1来真实反映各节点到其他所有节点的路径长度（权值大小） 。其数据结构定义为：typedef structchar* vexs_V; /顶点向量int arcs_V_V;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数MGraph;2.2 功能模块定义2.2.1 无向图构造模块根据实际情况设计学校平面图（至少包含 10 个地点） ，
5、并采用邻接矩阵实现对该平面图节点及权值信息的存储3。包括：各定点的名称（地点名） ，各个节点到其他所有节点的真实路径长度（赋权值）4。即对无向图两点间的边值赋值。本课程设计中涉及地点编号及信息如下：1 南门 2 行政楼 3 学生会堂 4 C 区 5 静明湖 6 图书馆 7 分析测试中心 8 第二教学楼 9 羽毛球场 10 励志楼 11 学生公寓中心 12 食堂区 13 医务室 14 凌云楼 15 篮球场 16 生化楼 17 东门 18 文德楼 19 排球场 20 第一教学楼 21 学生活动中心 22 足球场 23 北门 24 西苑 25 学生洗涤中心 26 开水房 27 自助服务点2.2.2
6、导航图建立模块根据课程设计功能要求设计人性化的导航界面，方便用户根据自己实际需要查询的信息选择相应的菜单，完成导航功能。主界面中应包括的选项有：1 两点最短距离导航 2 某点到其他所有点的最短距离 3 退出导航系统 选择功能号后，还应提示用户输入待查地点编号信息。2.2.3 求最短路径模块本模块的基本思想是采用迪杰斯特拉算法2求最短路径，是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。2.2.4 主函数模块主函数模块是整个程序的入口，包括对各变量、数据结构以及要使用的函数的声明等。主函数中其他功能函数
7、调用有一定的顺序。首先调用导航图的建立函数，构建可视化导航菜单；然后获取用户的输入，并根据输入调用相应的功能函数，实现导航系统的功能。3 流程图3.1 系统运行流程图3.2 迪杰斯特拉算法流程图图 3.2 迪杰斯特拉算法流程图4 功能模块代码实现4.1 创建无向图函数int CreateUDN MGraph 作用：使 0 号定点命名为“南门” ； G.arcs01 G.arcs10 20;作用：使 0 号节点到 1 号节点的路径赋值为 20，应为是无向图，所以 1 号节点到 0 号节点的路径长度也应赋值为 20。具体赋值如下：G.arcs01 G.arcs10 20;G.arcs05 G.ar
8、cs50 100;G.arcs06 G.arcs60 80;G.arcs12 G.arcs21 50;G.arcs23 G.arcs32 200; G.arcs24 G.arcs42 50;G.arcs34 G.arcs43 200;G.arcs323 G.arcs233 1500;G.arcs45 G.arcs54 20;G.arcs56 G.arcs65 80; G.arcs67 G.arcs76 80;G.arcs78 G.arcs87 50;G.arcs79 G.arcs97 60; G.arcs810 G.arcs108 220;G.arcs818 G.arcs188 200; G.
9、arcs821 G.arcs218 130;G.arcs1011 G.arcs1110 150; G.arcs1025 G.arcs2510 120;G.arcs1112 G.arcs1211 120;G.arcs1213 G.arcs1312 20;G.arcs1226 G.arcs2612 150;G.arcs1314 G.arcs1413 50;G.arcs1315 G.arcs1513 100;G.arcs1317 G.arcs1713 70;G.arcs1320 G.arcs2013 30;G.arcs1324 G.arcs2413 20;G.arcs1415 G.arcs1514
10、70;G.arcs1416 G.arcs1614 100;G.arcs1516 G.arcs1615 60; G.arcs1517 G.arcs1715 50;G.arcs1718 G.arcs1817 80;G.arcs1719 G.arcs1917 120;G.arcs1819 G.arcs1918 110; G.arcs1820 G.arcs2018 50;G.arcs1921 G.arcs2119 100;G.arcs1922 G.arcs2219 80; G.arcs2024 G.arcs2420 20;G.arcs2526 G.arcs2625 30;导航菜单生成void menu
11、 函数描述：输出各个节点的编号，及本系统所提供的查询方式，方便导航。具体导航菜单设计如下：void menu printf “ 导航主菜单 n“ ;printf “ 1 南门 2 行政楼 3 学生会堂 n“ ;printf “ 4 C 区 5 静明湖 6 图书馆 n“ ;printf “ 7 分析测试中心 8 第二教学楼 9 羽毛球场 n“ ;printf “ 10 励志楼 11 学生公寓中心 12 食堂区 n“ ;printf “ 13 医务室 14 凌云楼 15 篮球场 n“ ;printf “ 16 生化楼 17 东门 18 文德楼 n“ ;printf “ 19 排球场 20 第一教学
12、楼 21 学生活动中心 n“ ;printf “ 22 足球场 23 北门 24 西苑 n“ ;printf “ 25 学生洗涤中心 26 开水房 27 自助服务点 n“ ;printf “ nn“ ;printf “请选择导航功能：n“ ;printf “n“ ;printf “ 1 两点最短距离导航 n“ ;printf “ 2 某点到其他所有点的最短距离 n“ ;printf “ 3 退出导航系统 n“ ;printf “n“ ;最短路径求解函数void ShortPath MGraph int final_V;int k 1;for v 0;v G.vexnum;+v /初始化finalv 0;dv G.arcsv0-1v;for w 0;w G.vexnum;+w pvw 0;if dv INFINITY pvv0-1 1;pvv 1;dv0-1 0;finalv0-1
