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

《弗洛伊德算法求解最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计任务书课程设计名称数据结构课程设计专业计算机科学与技术（物联网方向）学生姓名班级学号题目名称最短路径求解起止日期2015年1月5日起至2015年1月16日止课设内容和要求：内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。要求：1)能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；2)利用矩阵保存城市间的距离；3)利用Floyd算法求最短路径；4)独立完成系统

2、的设计，编码和调试；5)系统利用C语言完成；6)按照课程设计规范书写课程设计报告。参考资料：《算法与数据结构》《C语言程序设计》教研室审核意见：教研室主任签字：指导教师（签名）年月日学生（签名）年月日目录第1章概要设计11.1题目的内容与要求11.2总体结构1第2章详细设计22.1主模块22.2构建城市无向图32.3添加城市42.4修改城市距离52.5求最短路径6第3章调试分析73.1调试初期73.2调试中期73.3调试末期7第4章测试及运行结果7附页（程序清单）10第1章概要设计1.1题目的内容与要求内容：给出一张无向

3、图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。要求：1)能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；2)利用矩阵保存城市间的距离；3)利用Floyd算法求最短路径；4)独立完成系统的设计，编码和调试；5)系统利用C语言完成；6)按照课程设计规范书写课程设计报告。1.2总体结构本程序主要分为四个模块（功能模块见图1.1）：主模块对整个程序起一主导作用，开始构建一城市无向图，对其

4、进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。添加城市顶点Floyd算法求最短路径修改城市距离求最短路径建城市图图1.1功能模块图第2章详细设计2.1主模块用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2：建立城市无向图2.3：添加城市2.4：修改城市距离2.5：求最短路径。流程图中通过输入n，由n的值

5、来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。图2.1主模块流程图开始输入选择n退出求最短路径修改城市距离建城市无向图图添加城市Exit退出程序调用各子函数结束2.2构建城市无向图根据提示输入城市，对城市无向矩阵图进行初始化，开始g.v[m][n].path的路径值赋为-2表示p城到q城间中间没有可达的路径不经过其他城市，而g.v[m][n].distance赋值为0表示p到p的距离为0。流程图中的MAX表示的是最多的城市数量，其值为20

6、；p，q表示城市的编号，而path和distance分别表示的路径和城市间距离。g.v[p][q].distace表示p、q代表的城市间的距离图2.2构建城市无向图流程图开始输入城市p=0,q=0q

7、经过其他城市。需注意的是当g.v[m][n].distance=0表示p城到q城的距离为0，当g.v[m][n].distance=99999，则表示p城到q城距离无穷大即表示他们之间无路径可达，而当g.v[m][n].distance=k(0

8、111输入disdistance=99999distance=disg.n++结束2.4修改城市距离根据屏幕上的城市编号，输入想更改的城市编号。在进行该模块时会输出原来的距离。由于在现实生活中由于一些人为的测量误差或是一些自然因素，又或是城市整编等等一系列的因素需要改动原来的城市距离，此时应用该块修改的功能即可实现更