校园最短路径问题的研究与实现 第页 共37页 校园最短路径问题的研究与实现 学生姓名： 指导老师： 摘 要 本课程设计主要解决求的校园任意地点间最短路径的问题。在本程序中，对于任意一个起点,如果不确定具体的终点,则以表格形式输出从起点到其他各地点的最短路径长度以及途经哪些地点；如果用户确定终点，则只输出从起点到具体地点的最短路径长度以及途经哪些地点。同时还能实现对校园路径图的修改功能，如顶点以及边的增删、边上权值的修改等。在程序设计中，采用Visual C+程序设计语言，以及Microsoft Visual C+ 6.0开发平台进行开发实现。 关键词 校园最短路径；起点；终点；路径图修改；C+ 目录1.引言3 1.1课程设计目的3 1.2概要设计32.详细设计52.1功能流程图52.2类的定义52.3功能函数实现72.4算法分析.142.5程序调试.143.测试运行.163.1开始界面测试.163.2输出顶点信息功能测试.163.3输出边信息功能测试.163.4修改功能测试.173.5求最短路径功能测试.173.6删除顶点功能测试.183.7插入顶点功能测试.193.8删除边功能测试.193.9插入边功能测试.203.10退出程序测试214.结束语.23参考文献.24附录：程序清单.251 引 言本课程设计主要解决校园最短路径的求取，校园中的各具体地点作为顶点，各顶点间的路径作为边，可实现对顶点及边的信息进行添加、删除及修改等功能，可显示各顶点及边的信息，可求出每一对顶点间的最短路径和单源点最短路径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）为了便于访问，用户可以先输出所有的地点及距离。（3）用户可以随意修改任意两点之间的距离。（4）用户可以任意增加及删除边。（5）当用户操作错误时，系统会出现出错提示。4.方案设计本程序采用Dijkstra算法实现最短路径的求解，因此，校园分布图采用邻接矩阵进行存储。在主程序中以菜单方式给出提示，进入各功能要求用户输入现在的位置，以及是否有确定的重点。主程序中对该图进行初始化，有一定的实验数据3。2 详细设计2.1功能流程图开始删除某个顶点插入某个边删除某个边顶点信息输出边信息输出修改求最短路径插入某个顶点01234567退出8图2.1系统功能流程图2.2 类的定义为构建图及最短路径建立了图的类，其类定义如下：const int MaxSize=12; /图中最多顶点个数template class Graphpublic: Graph(int* a, T* v,int n ); /构造函数，初始化具有n个顶点的图 Graph( ) /析构函数 void Dijkstra( int v,int endv); /最小距离 void PutOutVexInfo(); /取顶点信息 void PutOutArcInfo(); /输出路径 void SetArc(int v1,int v2,int arclength); /修改路径 void DeleteVex(int pos); /删除顶点pos的信息 void InsertVex(int num,T name); /在num的位置上插入一顶点，值为name void DeleteArc(int i, int j); /在图中删除一条边，其依附的两个顶点的编号为i和j void InsertArc(int i, int j,int n); /在图中插入一条边，其依附的两个顶点的编号为i和jprivate: T vertexMaxSize; /存放图中顶点的数组 int arcMaxSizeMaxSize; /存放图中边的数组 int vertexNum; /图的顶点数和边数 ;#endif在图的类中，提供了如下成员函数：（1）函数声明：Graph 完成的功能：构造函数，初始化具有n个顶点的图（2）函数声明：void Dijkstra 完成的功能：求最短距离（3）函数声明：PutOutVexInfo完成的功能： 取顶点信息 （4）函数声明：PutOutArcInfo 完成的功能：取边信息（5）函数声明：SetArc完成的功能： 修改路径 （6）函数声明：DeleteVex 完成的功能：删除某顶点的信息（7）函数声明：InsertVex 完成的功能：插入某个顶点（8）函数声明：DeleteArc 完成的功能：删除某边的信息（9）函数声明：InsertArc完成的功能：插入某边及相应顶点2.3 功能函数实现1.构造函数定义前置条件：图不存在输入：无 功能：图的初始化输出：无后置条件：构造一个有值的图Graph:Graph(int* a,T* v, int n ) /构造图 int i,j; vertexNum=n; /顶点数 for (i=0; iMaxSize; i+) /初始化邻接矩阵 for (j=0; jMaxSize; j+) /定义边 arcij = 10000; for ( i=0; ivertexNum; i+) vertexi=vi; /存储顶点信息 for (i=0; ivertexNum; i+) /给边赋置 for (j=0; jvertexNum; j+) arcij=*(a+i*n+j); int tt=0;2.取顶点信息函数定义前置条件：图已存在输入：无功能：输出图中所有顶点的数据信息输出：图中所有顶点的数据信息后置条件：图保持不变 void Graph:PutOutVexInfo() /取顶点 int i=0; /假设源点是第0个顶点，即顶点序号是0 if (ivertexNum) throw 位置; /错误抛出异常 elsefor(i=0;ivertexNum;i+) /输出图中所有的顶点 coutvertexin; 3.修改路径函数定义前置条件：图已存在输入：顶点v1,v2功能：修改顶点v1、v2的路径输出：修改后图中所有的路径后置条件：图保持不变void Graph:SetArc(int v1,int v2,int arclength) /修改路径 /假设源点是第0个顶点，即顶点序号是0if ( v1vertexNum| v2ver