文档介绍：算法课程设计-利用迪杰斯特拉算法实现无向图的最短路径的计算和求解
摘要
本次课程设计主要核心为利用迪杰斯特拉算法实现无向图的最短路径的计算和求解。要求理解迪杰斯特拉算法的具体实现流程、学会正确使用该算法求解实际问题。本次课程设计具体内容是:为自己学校建立一个校园导航系统。该系统应该具有:查询任意两点最短路径以及查询任意一点到其他各点的最短路径。
本程序要求结合最短路径迪杰斯特拉算法以及相应的数据结构的定义和使用,实现一个最短路径算法的简单应用。本文主要包括的函数模块有:数据结构定义、无向图的建立、导航图建立、最短路径求解及主函数模块。还有运行调试过程的截图,最后附上程序清单,以供查阅。
本课程设计是对书本知识的简单应用,以此培养大家用书本知识解决实际问题培养实际工作所需要的动手能力以科学理论和工程上的技术,规范地开发大型、复杂、高质量的应用软件和系统软件
目录
摘要 I
1 问题描述 1
2 方案设计 2
数据结构定义模块 2
功能模块定义 2
无向图构造模块 2
导航图建立模块 2
求最短路径模块 3
主菜单 3
3 流程图 4
系统运行流程图 4
迪杰斯特拉算法流程图 5
4 功能模块代码实现 6
创建无向图函数 6
导航菜单生成 7
最短路径求解函数 8
5 运行调试 11
查询系统导航界面 11
两点最短距离导航 11
某点到其他所有点最短距离 12
退出系统 12
6 程序设计总结 13
7 参考文献 14
附录程序清单 15
问题描述
这是一个最短路径算法的简单应用,体现了理论与实际的结合。在完成本系统过程中,应用所学知识解决具体的实际问题。
根据本设计要求,首先应该根据本学校的具体实际,建立校园平面图。然后根据该图建立无向图的邻接矩阵,矩阵的值表示两点之间的实际距离。最后根据用户请求调用迪杰斯特拉算法,并输出相应的路径信息。
该系统还应该设计可视化导航键面,方便用户使用。根据本课程设计要求,本系统应该具备如下功能:
1、查询任意两点间的最短路径(包括途经地点以及最短距离);
2、查询任意一点到其他各点的最短路径(包括途经地点以及最短距离);
3、能完成连续的查询工作;
4、用户查询完后能方便的退出程序系统。
方案设计
数据结构定义模块
本模块定义了导航图中各个节点的基本结构类型,主要采用邻接矩阵的存储结构[1]来真实反映各节点到其他所有节点的路径长度(权值大小)。
其数据结构定义为:
typedef struct
char* vexs[_V]; //顶点向量
int arcs[_V][_V];//邻接矩阵
int vexnum,um;//图的当前顶点数和弧数
MGraph;
功能模块定义
无向图构造模块
根据实际情况设计学校平面图(至少包含10个地点),并采用邻接矩阵实现对该平面图节点及权值信息的存储[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 自助服务点
导航图建立模块
根据课程设计功能要求设计人性化的导航界面,方便用户根据自己实际需要查询的信息选择相应的菜单,完成导航功能。
主界面中应包括的选项有:
1 两点最短距离导航
2 某点到其他所有点的最短距离
3 退出导航系统
选择功能号后,还应提示用户输入待查地点编号信息。
求最短路径模块
本模块的基本思想是采用迪杰斯特拉算法[2]求最短路径,是本校园导航系统的核心模块,求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用,进而实现导航功能。
主函数模块
主函数模块是整个程序的入口,包括对各变量、数据结构以及要使用的函数的声明等。
主函数中其他功能函数调用有一定的顺序。首先调用导航图的建立函数,构建可视化导航菜单;然后获取用户的输入,并根据输入调用相应的功能函