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

《校园最短路径问题的研究与实现》第１页共37页校园最短路径问题的研究与实现学生姓名：指导老师：摘要本课程设计主要解决求的校园任意地点间最短路径的问题。在本程序中，对于任意一个起点,如果不确定具体的终点,则以表格形式输出从起点到其他各地点的最短路径长度以及途经哪些地点；如果用户确定终点，则只输出从起点到具体地点的最短路径长度以及途经哪些地点。同时还能实现对校园路径图的修改功能，如顶点以及边的增删、边上权值的修改等。在程序设计中，采用VisualC++程序设计语言，以及MicrosoftVisualC++6.0开发平台进行开发实现。关键词校园最短路径；起点；终点；路径图修改；C++《校园最短路径问题的研究与实现》第２页共37页目录1.引言………………………………………………………………………………31.1课程设计目的………………………………………………………………………………31.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附录：程序清单………………………………………………………………….25《校园最短路径问题的研究与实现》第３页共37页1引言本课程设计主要解决校园最短路径的求取，校园中的各具体地点作为顶点，各顶点间的路径作为边，可实现对顶点及边的信息进行添加、删除及修改等功能，可显示各顶点及边的信息，可求出每一对顶点间的最短路径和单源点最短路径[1]。1.1课程设计目的1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学工作方法和作风[2]。1.2概要设计1.问题描述图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。校园最短路径问题中的数据元素有：（1）顶点数（2）边数（3）边的长度2.功能需求要求完成以下功能：（1）输出顶点信息：将校园内各位置输出。（2）输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。（3）修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；《校园最短路径问题的研究与实现》第４页共37页（4）求最短路径：输出给定两点之间的最短路径的长度及途经的地点或输出任意一点与其他各点的最短路径。（5）删除：删除任意一条边。（6）插入：插入任意一条边。3.实现要点（1）对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边均设置了初值。（2）为了便于访问，用户可以先输出所有的地点及距离。（3）用户可以随意修改任意两点之间的距离。（4）用户可以任意增加及删除边。（5）当用户操作错误时，系统会出现出错提示。4.方案设计本程序采用Dijkstra算法实现最短路径的求解，因此，校园分布图采用邻接矩阵进行存储。在主程序中以菜单方式给出提示，进入各功能要求用户输入现在的位置，以及是否有确定的重点。主程序中对该图进行初始化，有一定的实验数据[3]。《校园最短路径问题的研究与实现》第５页共37页2详细设计2.1功能流程图图2.1系统功能流程图2.2类的定义为构建图及最短路径建立了图的类，其类定义如下：constintMaxSize=12;//图中最多顶点个数templateclassTclassGraph{public:Graph(int*a,T*v,intn);//构造函数，初始化具有n个顶点的图~Graph(){}//析构函数voidDijkstra(intv,intendv);//最小距离voidPutOutVexInfo();//取顶点信息voidPutOutArcInfo();//输出路径voidSetArc(intv1,intv2,intarclength);//修改路径voidDeleteVex(intpos);//删除顶点pos的信息开始删除某个顶点插入某个边删除某个边顶点信息输出边信息输出修改求最短路径插入某个顶点01234567退出8《校园最短路径问题的研究与实现》第６页共37页voidInsertVex(intnum,Tname);//在num的位置上插入一顶点，值为namevoidDeleteArc(inti,intj);//在图中删除一条边，其依附的两个顶点的编号为i和jvoidInsertArc(inti,intj,intn);//在图中插入一条边，其依附的两个顶点的编号为i和jprivate:Tvertex[MaxSize];//存放图中顶点的数组intarc[MaxSize][MaxSize];//存放图中边的数组intvertexNum;//图的顶点数和边数};#endif在图的类中，提供了如下成员函数：（1）函数声明：Graph完成的功能：构造函数，初始化具有n个顶点的图（2）函数声明：voidDijkstra完成的功能：求最短距离（3）函数声明：PutOutVexInfo完成的功能：取顶点信息（4）函数声明：PutOutArcInfo完成的功能：取边信息（5）函数声明：SetArc完成的功能：修改路径（6）函数声明：DeleteVex完成的功能：删除某顶点的信息（7）函数声明：InsertVex完成的功能：插入某个顶点（8）函数声明：DeleteArc完成的功能：删除某边的信息（9）函数声明：InsertArc完成的功能：插入某边及相应顶点《校园最短路径问题的研究与实现》第７页共37页2.3功能函数实现1.构造函数定义前置条件：图不存在输入：无功能：图的初始化输出：无后置条件：构造一个有值的图GraphT::Graph(int*a,T*v,intn)//构造图{inti,j;vertexNum=n;//顶点数for(i=0;iMaxSize;i++)//初始化邻接矩阵for(j=0;jMaxSize;j++)//定义边arc[i][j]=10000;for(i=0;ivertexNum;i++)vertex[i]=v[i];//存储顶点信息for(i=0;ivertexNum;i++)//给边赋置for(j=0;jvertexNum;j++)arc[i][j]=*(a+i*n+j);inttt=0;}2.取顶点信息函数定义前置条件：图已存在输入：无功能：输出图中所有顶点的数据信息输出：图中所有顶点的数据信息后置条件：图保持不变voidGraphT::PutOutVexInfo()//取顶点{《校园最短路径问题的研究与实现》第８页共37页inti=0;//假设源点是第0个顶点，即顶点序号是0if(ivertexNum)throw位置;//错误抛出异常else{for(i=0;ivertexNum;i++){//输出图中所有的顶点coutvertex[i]\n;}}}3.修改路径函数定义前置条件：图已存在输入：顶点v1,v2功能：修改顶点v1、v2的路径输出：修改后图中所有的路径后置条件：图保持不变voidGraphT::SetArc(intv1,intv2,intarclength)//修改路径{//假设源点是第0个顶点，即顶点序号是0if(v1vertexNum||v2vertexNum)throw位置;//错误抛出异常else{arc[v1][v2]=arclength;//修改v1顶点到v2顶点的距离arc[v2][v1]=arclength;}}4.取边函数定义前置条件：图已存在输入：无功能：输出图中所有的路径输出：图中所有顶点的数据信息后置条件：图保持不变voidGraphT::PutOutArcInfo()//输出图中所有的路径{inti=0;//假设源点是第0个顶点，即顶点序号是0intj=0;《校园最短路径问题的研究与实现》第９页共37页if(ivertexNum||jvertexNum)throw位置;//错误抛出异常else{for(i=0;ivertexNum;i++){//输出任意两点之间的路径for(j=0;ji;j++){if(arc[i][j]10000)//两点之间存在路径cout从vertex[i]到vertex[j]的路径长度为：arc[i][j]\n;//若两点间有路，则输出该两点间的路径}}}}5.插入顶点函数定义前置条件：图已存在输入：顶点name,位置i功能：在图中i位置插入一个顶点name输出：如果插入不成功，抛出异常后置条件：如果插入成功，图中增加了一个顶点voidGraphT::InsertVex(intnum,Tname)//在图中插入一个顶点，其编号为i，值为value{//假设源点是第0个顶点，即顶点序号是0if(num0||numvertexNum)throw位置;//如果num输入不正确抛出异常introw;//行intcol;//列intnumv;//最后一个顶点所在的位置numv=vertexNum-1;if(num-1)//num存在vertexNum++;//顶点数加1for(inti=numv;inum-1;i--)//i从最后一个顶点的下一个位置开始循环vertex[i]=vertex[i-1];//把从num位置的顶点到最后一个顶点均向后移一位vertex[num]=name;//把要插入的顶点的值放在num位置上for(row=numv;row=0;row--)//把从num列到最后一列的元素均向下移一列《校园最短路径问题的研究与实现》第１０页共37页{for(col=numv;col=num;col--)arc[row][col+1]=arc[row][col];arc[row][num]=10000;}for(row=numv;row=num;row