课程设计任务书课程设计名称 数据结构课程设计专业计算机科学与技术（物联网方向）学生姓名班级学号题目名称最短路径求解起止日期2015年1月5日起至2015年1月16日止课设内容和要求：内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。要求： 1) 能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；2) 利用矩阵保存城市间的距离；3) 利用Floyd算法求最短路径；4) 独立完成系统的设计，编码和调试；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题目的内容与要求内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。要求： 1) 能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；2) 利用矩阵保存城市间的距离；3) 利用Floyd算法求最短路径；4) 独立完成系统的设计，编码和调试；5) 系统利用C语言完成；6) 按照课程设计规范书写课程设计报告。1.2总体结构 本程序主要分为四个模块（功能模块见图1.1）：主模块对整个程序起一主导作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。添加城市顶点Floyd算法求最短路径修改城市距离求最短路径建城市图图1.1 功能模块图-I-沈阳航空航天大学课程设计报告 第2章 详细设计2.1主模块用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2：建立城市无向图2.3：添加城市2.4：修改城市距离2.5：求最短路径。流程图中通过输入n，由n的值来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。图2.1 主模块流程图 开始输入选择n退出求最短路径修改城市距离建城市无向图图添加城市Exit 退出程序调用各子函数结束2.2构建城市无向图 根据提示输入城市，对城市无向矩阵图进行初始化，开始g.vmn.path的路径值赋为-2表示p城到q城间中间没有可达的路径不经过其他城市，而g.vmn.distance赋值为0表示p到p的距离为0。流程图中的MAX表示的是最多的城市数量，其值为20；p，q表示城市的编号，而path和distance分别表示的路径和城市间距离。g.vpq.distace表示p、q代表的城市间的距离 图2.2 构建城市无向图流程图开始 输入城市p=0,q=0qMAX 否 是PMAX 否 是g.vpq.path=-2;g.vqq.distance=0return g结束 2.3添加城市 用户根据提示输入想要添加到无向图中的城市，根据屏幕中的提示输入与之邻接的城市间的距离，然后添加城市距离矩阵图中；同时将g.vmn.path赋值为-1即表示p城到q城有路可达且最短路径无需经过其他城市。需注意的是当g.vmn.distance=0表示p城到q城的距离为0，当g.vmn.distance=99999，则表示p城到q城距离无穷大即表示他们之间无路径可达，而当g.vmn.distance=k(0k99999)时表示他们间的距离是k。流程图中g.n表示当前图中存储的城市数量，dis表示输入的城市间的距离即q和g.n表示城市间的距离。通过qg.n的条件判断来充分完成图对应的矩阵中的赋值。图2.3 添加城市流程图开始 输入城市 p=q=0qm,则d(vi,vj)=m,否则为k，依次类推，直到所有的vi到vj的中间城市比较完，最后d(vi,vj)的值即为最短距离，同时在比较的过程中保存路径信息，最后在查询时即可输出路径。具体见第四章：测试及运行结果中求最短路径界面图2.4 修改城市距离流程图开始i=j=k=0kg.n-1 否 是ig.n-1 否 是 jg.vik.distance+g.vkj.distance; 是 是 g.vij.distance=g.vik.distance+g.vkj.distance path=kj+ k+ i+ 输入城市求路径第3章 调试分析3.1 调试初期 由于编写的程序具有模块化的特性，且VC 6.0 的调试显然由于TC及个人对VC的熟练程度远优于TC等方面，我选择先在VC 6.0环境下完成除图形化演示算法过程函数的其他过程。由于数据结构选择的较合理，对Floyd算法的理解较为深刻，所以在此环境下的调试并没有太多困难。3.2 调试中期在上机输入完程序后，出现了许多错误，其中有一些小错误，比如说忘记写分号，在这些错误上双击，找到位置，加上分号。还有就是程序中的有的变量在前面没有定义，只要在前面添加上就可以了。再有就是前后的类型要保持一致，在这