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

《校园最短路径问题的研究与实现》由会员分享，可在线阅读，更多相关《校园最短路径问题的研究与实现（38页珍藏版）》请在装配图网上搜索。

1、 校园最短路径问题的研究与实现 第页 共38页 校园最短路径问题的研究与实现 学生姓名： 指导老师： 摘 要 本课程设计主要解决求的校园任意地点间最短路径的问题。在本程序中，对于任意一个起点,如果不确定具体的终点,则以表格形式输出从起点到其他各地点的最短路径长度以及途经哪些地点；如果用户确定终点，则只输出从起点到具体地点的最短路径长度以及途经哪些地点。同时还能实现对校园路径图的修改功能，如顶点以及边的增删、边上权值的修改等。在程序设计中，采用Visual C+程序设计语言，以及Microsoft Visual C+ 6.0开发平台进行开发实现。 关键词 校园最短路径；起点；终点；路径图修改；C

2、+ 目录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 引 言本课程设计主要解决校园最短路径的求取，校园中的各具体地点作为顶点，各顶点间的路径作为

3、边，可实现对顶点及边的信息进行添加、删除及修改等功能，可显示各顶点及边的信息，可求出每一对顶点间的最短路径和单源点最短路径1。1.1 课程设计目的1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学工作方法和作风2。1.2 概要设计1.问题描述图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的

4、地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。校园最短路径问题中的数据元素有：（1）顶点数（2）边数（3）边的长度2.功能需求要求完成以下功能：（1）输出顶点信息：将校园内各位置输出。（2）输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。（3）修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离；（4）求最短路径：输出给定两点之间的最短路径的长度及途经的地点或输出任意一点与其他各点的最短路径。（5）删除：删除任意一条边。（6）插入：插入任意一条边。3.实现要点（1）对图的

5、创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边均设置了初值。（2）为了便于访问，用户可以先输出所有的地点及距离。（3）用户可以随意修改任意两点之间的距离。（4）用户可以任意增加及删除边。（5）当用户操作错误时，系统会出现出错提示。4.方案设计本程序采用Dijkstra算法实现最短路径的求解，因此，校园分布图采用邻接矩阵进行存储。在主程序中以菜单方式给出提示，进入各功能要求用户输入现在的位置，以及是否有确定的重点。主程序中对该图进行初始化，有一定的实验数据3。2 详细设计2.1功能流程图开始删除某个顶点插入某个边删除某个边顶点信息输出边信息

6、输出修改求最短路径插入某个顶点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 v

7、1,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; /

8、存放图中边的数组 int vertexNum; /图的顶点数和边数 ;#endif在图的类中，提供了如下成员函数：（1）函数声明：Graph 完成的功能：构造函数，初始化具有n个顶点的图（2）函数声明：void Dijkstra 完成的功能：求最短距离（3）函数声明：PutOutVexInfo完成的功能： 取顶点信息 （4）函数声明：PutOutArcInfo 完成的功能：取边信息（5）函数声明：SetArc完成的功能： 修改路径 （6）函数声明：DeleteVex 完成的功能：删除某顶点的信息（7）函数声明：InsertVex 完成的功能：插入某个顶点（8）函数声明：DeleteArc 完成

9、的功能：删除某边的信息（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; i

10、vertexNum; 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.修改路径函数定义前置条件

11、：图已存在输入：顶点v1,v2功能：修改顶点v1、v2的路径输出：修改后图中所有的路径后置条件：图保持不变void Graph:SetArc(int v1,int v2,int arclength) /修改路径 /假设源点是第0个顶点，即顶点序号是0if ( v1vertexNum| v2vertexNum) throw 位置; /错误抛出异常 elsearcv1v2=arclength; /修改v1顶点到v2顶点的距离arcv2v1=arclength;4.取边函数定义前置条件：图已存在输入：无功能：输出图中所有的路径输出：图中所有顶点的数据信息后置条件：图保持不变void Graph:Pu

12、tOutArcInfo() /输出图中所有的路径 int i=0; /假设源点是第0个顶点，即顶点序号是0 int j=0;if ( ivertexNum| jvertexNum) throw 位置; /错误抛出异常 else for(i=0;ivertexNum;i+) /输出任意两点之间的路径 for(j=0;ji;j+) if(arcij10000) /两点之间存在路径 cout从vertexi到vertexj的路径长度为：arcijn; /若两点间有路，则输出该两点间的路径 5.插入顶点函数定义前置条件：图已存在输入：顶点name,位置i功能：在图中i位置插入一个顶点name 输出：如

13、果插入不成功，抛出异常后置条件：如果插入成功，图中增加了一个顶点void Graph:InsertVex(int num,T name) /在图中插入一个顶点，其编号为i，值为value /假设源点是第0个顶点，即顶点序号是0 if ( numvertexNum) throw 位置; /如果num输入不正确抛出异常 int row; /行 int col; /列 int numv; /最后一个顶点所在的位置numv = vertexNum-1; if(num-1) /num存在 vertexNum+; /顶点数加1for(int i=numv;inum-1;i-) /i从最后一个顶点的下一个位

14、置开始循环vertexi=vertexi-1; /把从num位置的顶点到最后一个顶点均向后移一位vertexnum=name; /把要插入的顶点的值放在num位置上 for(row=numv;row=0;row-) /把从num列到最后一列的元素均向下移一列 for(col=numv;col=num;col-) arcrowcol+1=arcrowcol; arcrownum=10000; for(row=numv;row=num;row-) /把从num行到最后一行的元素均向下移一行 for(col=0;col=numv+1;col+) arcrow+1col=arcrowcol;for(c

15、ol=0;colvertexNum;col+) arcnumcol=10000; /把num位置所在的行、列的值均置为无穷大6.删除顶点函数的定义前置条件：图已存在输入：顶点pos 功能：在图中删除顶点pos 输出：如果删除不成功，抛出异常后置条件：如果删除成功，图中减少了一个顶点,相应顶点所建立的边也消去void Graph:DeleteVex(int pos) /删除第pos个顶点 /假设源点是第0个顶点，即顶点序号是0 if ( posMaxSize) throw 位置; /如果pos输入不正确抛出异常 int row; /行 int col; /列 int numv=vertexNum

16、; /numv等于顶点数 if(pos-1) /pos存在 for(int i=pos;inumv-1;i+) vertexi=vertexi+1; /把从pos到最后的每个点的位置依次向前移一位 vertexNum-; /顶点数减1 for(row=0;rownumv;row+) for(col=pos;colnumv;col+)arcrowcol=arcrowcol+1; /把从pos列到最后一列的元素均向前移一列 arcrownumv-1=10000; /把pos所在的列上的值置为无穷大 for(row=pos;rownumv;row+) for(col=0;colnumv;col+)a

17、rcrowcol=arcrow+1col; /把从pos行到最后一行的元素均向上移一行 7.求最短距离函数定义前置条件：图已存在输入：顶点v ，endv功能：假如endv存在，求v到endv的最短路径；假如不输入endv，则求v到任意顶点的最短路径 输出：所求得的最短路径及所经历的位置后置条件：图保持不变void Graph:Dijkstra(int v,int endv) /求最短路径，从v顶点到endv点的最短路径 if ( vvertexNum) throw 位置; /v顶点或endv顶点输出不正确则抛出异常 int numv=vertexNum; /顶点数 int distMaxSiz

18、e; /最短长度 int pathMaxSize; /当前找到的最短路径 int sMaxSize; /存放源点和已生成的终点的集合 int max= 10000; /代表无穷大int i,j,k,wm; for(i=0;inumv;i+) /按网的邻接矩阵确定各顶点最短路径的初值 disti=arcvi; if(i!=v& disti max) /如果v、i之间有路 pathi=v; /当前找到的最短路径为v else pathi=-1; /否则v与i顶点不存在路径 si = 0; /给s集合确定初值0 sv=1;distv=0; /将顶点v本身排除在外 for(k =0;knumv-1;k

19、+) /求其他numv-1各顶点的最短路径 wm = max;j=v; /确定当前最短路径wm及顶点的序号j for( i=0;inumv;i+) if(!si&distiwm) /如果v、i之间有路 j=i;wm = disti; /把当前找到的路径确定为最大值 sj=1; for(i =0;inumv;i+) /更新未确定最短路径各顶点的当前最短路径 if(!si&distj+arcjidisti) /如果v、i两点的距离加上i、j小于从v点到j点的距离 disti=distj+arcji;pathi=j; /disti取最小值 if (endv =0 ) /endv点存在 string

20、mmm=; /初始化字符串 int j =endv; while(j -1 ) string nnn = vertexj; /依次把顶点存放在nnn字符串中 nnn+=mmm; mmm = +nnn; j = pathj; cout从 vertexv.c_str() 到 vertexendv.c_str() 的最短路径长度：distendv 路径：mmm.c_str()n;/输出从v点到endv点的最短路径 else /endv点不存在for(i=0;i -1 ) string nnn = vertexj; /依次把顶点存放在nnn字符串中 nnn+=mmm; mmm = +nnn; j =

21、pathj; cout从 vertexv.c_str() 到 vertexi.c_str() 的最短路径长度：disti 路径：mmm.c_str()n;/输出从v点到任意点的最短路径 8.删除边信息函数定义前置条件：图已存在输入：顶点n、w 功能：在图中删除顶点n、w 依附的边 输出：如果删除不成功，抛出异常后置条件：如果删除成功，图中减少了一条边void Graph:DeleteArc(int n, int w) /删除i、j两顶点依附的边if ( nMaxSize| wMaxSize) throw 位置; /如果输入不正确抛出异常 arcnw=arcwn=10000; /删除w顶点和n顶

22、点之间的路径9.插入边及相应顶点函数定义前置条件：图已存在输入：顶点i、j功能：在图中插入顶点i、j及其所依附的边 输出：如果插入不成功，抛出异常后置条件：如果插入成功，图中增加了一条边void Graph:InsertArc(int i, int j,int n) /在图中插入一条边，其依附的两个顶点的编号为i和jif ( iMaxSize| jMaxSize) throw 位置; /如果输入不正确抛出异常 arcij=n; arcji=n; cout从vertexi到vertexj的路径长度为：arcijvertexNum) throw 位置;此句可防止位置超出范围。此类问题还发生在该程序

23、的类封装的各程序中，都采用相同的办法解决范围超出问题。在求最短路径函数void Dijkstra(int v,int endv)中，求v顶点到endv点的最短路径时，两点间可能不存在路径，此时程序运行结果会异常。解决办法是先判断两点间是否有路径，再输出最短路径，用语句if(i!=v& disti max)来列出有路径的条件，否则即无路径。3 测试运行3.1开始界面测试开始界面如图3.1所示。图3.1开始界面3.2输出顶点信息功能测试根据菜单提示输入0执行顶点信息输出功能，则显示各顶点信息如图3.2所示。图3.2顶点输出功能测试结果则程序能正确输出各顶点信息。3.3输出边信息功能测试根据菜单提示

24、输入1执行边信息输出功能，则显示各顶点信息如图3.3所示。图3.3边信息输出功能测试结果则程序能正确输出各边信息。3.4修改功能测试根据菜单提示输入2执行修改功能，即可对两顶点间的距离进行修改，然后输入要修改的两顶点，再输入修改的距离值，执行结果如图3.4所示。图3.4修改功能测试结果此时则成功修改了两顶点间的距离。3.5求最短路径功能测试根据菜单提示输入3执行求最短路径功能，首先提示输入源顶点，输入始点后再提示“请输入结束顶点，若要全部显示请输入88:”，分别输入结束点和88后，则输出相应的最短路径信息，运行结果如图3.5和图3.6所示。图3.5输入结束点求最短路径运行结果图3.6输入88求

25、最短路径运行结果分别正确显示了有结束点和无结束点时最短路径。3.6删除顶点功能测试根据菜单提示输入4执行删除顶点功能，提示输入要删除的顶点，运行如图3.7所示。图3.7删除顶点功能运行结果运行删除该顶点成功。3.7插入顶点功能测试根据菜单提示输入5执行插入顶点功能，提示输入要插入的顶点的位置和名称，运行如图3.8所示。图3.8插入顶点功能测试再根据菜单中提示输入0执行输出顶点信息功能，输出结果如图3.9所示。图3.9插入顶点后顶点信息输出则插入顶点信息成功。3.8删除边功能测试根据菜单提示输入6执行删除边功能，提示输入两个顶点,即要删除边的顶点,输入顶点后运行结果如图3.10所示。图3.10删

26、除边功能测试再选择输入1，进入边信息输出功能，输出各边信息结果如图3.11所示。图3.11删除边后边信息输出结果顶点为1，2的边被删除，删除指定边功能运行成功。3.9插入边功能测试根据菜单提示输入7执行插入边功能，提示输入两个顶点，输入顶点后提示输入路径，在输入路径则显示相应插入边路径信息，运行入图3.12所示。图3.12插入边功能测试结果再选择输入1，进入边信息输出功能，输出各边信息结果如图3.13所示。图3.13插入边后边信息输出结果边（4，5）的信息被插入，插入边功能运行成功。3.10退出程序测试根据菜单提示输入8退出程序，运行结果如图3.14所示。图3.14退出程序测试结果退出程序成功

27、。4结束语课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。回顾起此次课程设计，我感慨颇多，的确，从理论到实践，在整整两星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固以前所学过的知识，而且学到了很多在书本上所没有学到过的知识或以前没有掌握的技能，如输入信息时从文件中读取相应内容的操作。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，将结论用于实践，从而提高自己的实际动手能力和独立思考的能力。

28、在设计的过程中当然遇到了问题，可以说得是困难重重，毕竟这是不可避免的，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说求最短路径的算法，迪杰斯特拉算法与弗洛伊德算法在具体程序中的运用，有逻辑错误时如何调试程序。同时，通过这次课程设计，把以前所学过的知识重新温故了。参考文献1王红梅，胡明，王涛. 数据结构（C+版）. 北京：清华大学出版社，20072 谭浩强. C+程序设计. 北京：清华大学出版社，20063 翁惠玉. C+程序设计思想与方法. 北京：人民邮电出版社，2008 附录：程序清单/ 程序名称：校园最短路径问题的研究与实现/ 程序功能：实

29、现最短路径的求取以及适当对路径图的修改等功能/ 程序作者：曾瑜琪/ 最后修改日期：2008-9-12#ifndef GRAPH_H /定义头文件#define GRAPH_H #include /引入标准库中的头文件using namespace std; const int MaxSize=12; /图中最多顶点个数template class Graphpublic: Graph(int* a, T* v,int n ); /构造函数，初始化具有n个顶点的图Graph( ) /析构函数 void Dijkstra( int v,int endv); /最小距离void PutOutVexI

30、nfo(); /取顶点信息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和jpriv

31、ate:T vertexMaxSize; /存放图中顶点的数组int arcMaxSizeMaxSize; /存放图中边的数组int vertexNum; /图的顶点数和边数;#endif#include#include /引入标准库中的头文件#include graph.h /引入头文件using namespace std;template Graph:Graph(int* a,T* v, int n ) /构造图 int i,j; vertexNum=n; /顶点数for (i=0; iMaxSize; i+) /初始化邻接矩阵 for (j=0; jMaxSize; j+) /定义边

32、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; template void Graph:PutOutVexInfo() /取顶点 int i=0; /假设源点是第0个顶点，即顶点序号是0 if (ivertexNum) throw 位置; /错误抛出异常elsefor(i=0;ivertexNum;i+) /输出图中所有的顶点 coutvertexi

33、n; template void Graph:SetArc(int v1,int v2,int arclength) /修改路径 /假设源点是第0个顶点，即顶点序号是0if ( v1vertexNum| v2vertexNum) throw 位置; /错误抛出异常 elsearcv1v2=arclength; /修改v1顶点到v2顶点的距离arcv2v1=arclength;template void Graph:PutOutArcInfo() /输出图中所有的路径 int i=0; /假设源点是第0个顶点，即顶点序号是0 int j=0;if ( ivertexNum| jvertexNum

34、) throw 位置; /错误抛出异常 else for(i=0;ivertexNum;i+) /输出任意两点之间的路径 for(j=0;ji;j+) if(arcij10000) /两点之间存在路径 cout从vertexi到vertexj的路径长度为：arcijn; /若两点间有路，则输出该两点间的路径 template void Graph:InsertVex(int num,T name) /在图中插入一个顶点，其编号为i，值为value /假设源点是第0个顶点，即顶点序号是0 if ( numvertexNum) throw 位置; /如果num输入不正确抛出异常 int row;

35、/行 int col; /列 int numv; /最后一个顶点所在的位置numv = vertexNum-1; if(num-1) /num存在 vertexNum+; /顶点数加1for(int i=numv;inum-1;i-) /i从最后一个顶点的下一个位置开始循环vertexi=vertexi-1; /把从num位置的顶点到最后一个顶点均向后移一位vertexnum=name; /把要插入的顶点的值放在num位置上 for(row=numv;row=0;row-) /把从num列到最后一列的元素均向下移一列 for(col=numv;col=num;col-) arcrowcol+1

36、=arcrowcol; arcrownum=10000; for(row=numv;row=num;row-) /把从num行到最后一行的元素均向下移一行 for(col=0;col=numv+1;col+) arcrow+1col=arcrowcol;for(col=0;colvertexNum;col+) arcnumcol=10000; /把num位置所在的行、列的值均置为无穷大template void Graph:DeleteVex(int pos) /删除第pos个顶点 /假设源点是第0个顶点，即顶点序号是0 if ( posMaxSize) throw 位置; /如果pos输入不

37、正确抛出异常 int row; /行 int col; /列 int numv=vertexNum; /numv等于顶点数 if(pos-1) /pos存在 for(int i=pos;inumv-1;i+) vertexi=vertexi+1; /把从pos到最后的每个点的位置依次向前移一位 vertexNum-; /顶点数减1 for(row=0;rownumv;row+) for(col=pos;colnumv;col+) arcrowcol=arcrowcol+1; /把从pos列到最后一列的元素均向前移一列 arcrownumv-1=10000; /把pos所在的列上的值置为无穷大

38、for(row=pos;rownumv;row+) for(col=0;colnumv;col+) arcrowcol=arcrow+1col; /把从pos行到最后一行的元素均向上移一行 template void Graph:Dijkstra(int v,int endv) /求最短路径，从v顶点到endv点的最短路径 if ( vvertexNum) throw 位置; /v顶点或endv顶点输出不正确则抛出异常 int numv=vertexNum; /顶点数 int distMaxSize; /最短长度 int pathMaxSize; /当前找到的最短路径 int sMaxSize

39、; /存放源点和已生成的终点的集合 int max= 10000; /代表无穷大int i,j,k,wm; for(i=0;inumv;i+) /按网的邻接矩阵确定各顶点最短路径的初值 disti=arcvi; if(i!=v& disti max) /如果v、i之间有路 pathi=v; /当前找到的最短路径为v else pathi=-1; /否则v与i顶点不存在路径 si = 0; /给s集合确定初值0 sv=1;distv=0; /将顶点v本身排除在外 for(k =0;knumv-1;k+) /求其他numv-1各顶点的最短路径 wm = max;j=v; /确定当前最短路径wm及顶点的序号j for( i=0;inumv;i+) if(!si&distiwm) /如果v、i之间有路 j=i;wm = disti; /把当前找到的路径确定为最大值 sj=1; for(i =0;in