校园最短路径问题的研究与实现.doc

校园最短路径问题的研究与实现 学生姓名： 指导老师： 摘 要 本课程设计主要解决求的校园任意地点间最短路径的问题。在本程序中，对于任意一个起点,如果不确定具体的终点,则以表格形式输出从起点到其他各地点的最短路径长度以及途经哪些地点；如果用户确定终点，则只输出从起点到具体地点的最短路径长度以及途经哪些地点。同时还能实现对校园路径图的修改功能，如顶点以及边的增删、边上权值的修改等。在程序设计中，采用Visual C++程序设计语言，以及Microsoft Visual C++ 6.0开发平台进行开发实现。 关键词 校园最短路径；起点；终点；路径图修改；C++  目录 1.引言………………………………………………………………………………3 1.1课程设计目的………………………………………………………………………………3 1.2概要设计……………………………………………………………………………………3 2.详细设计…………………………………………………………………………5 2.1功能流程图…………………………………………………………………………………5 2.2类的定义……………………………………………………………………………………5 2.3功能函数实现………………………………………………………………………………7 2.4算法分析…………………………………………………………………………………..14 2.5程序调试…………………………………………………………………………………..14 3.测试运行………………………………………………………………………..16 3.1开始界面测试……………………………………………………………………………..16 3.2输出顶点信息功能测试…………………………………………………………………..16 3.3输出边信息功能测试……………………………………………………………………..16 3.4修改功能测试……………………………………………………………………………..17 3.5求最短路径功能测试……………………………………………………………………..17 3.6删除顶点功能测试………………………………………………………………………..18 3.7插入顶点功能测试………………………………………………………………………..19 3.8删除边功能测试…………………………………………………………………………..19 3.9插入边功能测试…………………………………………………………………………..20 3.10退出程序测试……………………………………………………………………………21 4.结束语…………………………………………………………………………..23 参考文献………………………………………………………………………….24 附录：程序清单………………………………………………………………….25  1 引 言 本课程设计主要解决校园最短路径的求取，校园中的各具体地点作为顶点，各顶点间的路径作为边，可实现对顶点及边的信息进行添加、删除及修改等功能，可显示各顶点及边的信息，可求出每一对顶点间的最短路径和单源点最短路径[1]。 1.1 课程设计目的 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学工作方法和作风[2]。 1.2 概要设计 1.问题描述 图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。 校园最短路径问题中的数据元素有： （1）顶点数 （2）边数 （3）边的长度 2.功能需求 要求完成以下功能： （1）输出顶点信息：将校园内各位置输出。 （2）输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。 （3）修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离； （4）求最短路径：输出给定两点之间的最短路径的长度及途经的地点或输出任意一点与其他各点的最短路径。 （5）删除：删除任意一条边。 （6）插入：插入任意一条边。 3.实现要点 （1）对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边均设置了初值。 （2）为了便于访问，用户可