最短路径实验报告

xie数据结构与算法实验院别：计算机科学与信息工程学院年级专业：2014级空间信息与数字技术姓名：杨哲庆学号：1420012138评语和成绩:2015年12月实验9最短路径实验9.1最短路径9.1.1实验的主要内容和目的①掌握有向图的邻接矩阵存储结构。②利用Dijkstr算法求最短路径。③利用Floyd算法求最短路径；9.1.2代码MGraph.h(MGraph类的声明)#if!defined(AFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CA2693733E3F__INCLUDED_)#defineAFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CA2693733E3F__INCLUDED_#if_MSC_VER1000#pragmaonce#endif//_MSC_VER1000constintMax=20;//图中最多顶点的个数templateclassTclassMGraph{public:MGraph();//默认构造函数voidDijkstra(intv);//djkstra算法最短路径voidFloyd();//floyd算法求最短路径voidFloyd_prinf();//输出经过floyd算法计算后的最短路径private:Tvertex[Max];//存放图中顶点信息的数组intarc[Max][Max];//邻接矩阵数组intvertexNum,arcNum;//顶点数和边数Tpath[Max];//记录dijkstra算法中的路径intdist[Max];//辅助数组，存储dijkstra算法中最小的值intlength[Max][Max];//存储floyd算法中的路径长度Tpath_Floyd[Max][Max];//记录dijkstra算法中的路径};#endifMGraph.cpp(MGraph类的实现)#includeiostreamusingnamespacestd;#includeMGraph.h#includestringtemplateclassTMGraphT::MGraph(){inti,j,k;cout请输入顶点的个数vertexNum：;cinvertexNum;cout请输入边的条数arcNum：;cinarcNum;for(i=0;ivertexNum;i++){cout请输入第i+1个顶点的信息\t;cinvertex[i];}for(i=0;ivertexNum;i++)for(j=0;jvertexNum;j++)//初始化图的邻接矩阵arc[i][j]=infinite;for(k=0;karcNum;k++)//存储图的边信息{intm,n,weight;cout请输入边的两个顶点的序号：;cinmn;cout请输入(m,n)的权值：;cinweight;arc[m][n]=weight;//单向记录点的边以及权值}}templateclassTvoidMGraphT::Dijkstra(intv){inti,j;for(i=0;ivertexNum;++i)//初始化dist数组和path数组{dist[i]=arc[v][i];if(dist[i]!=infinite)path[i]=vertex[v]+-+vertex[i];elsepath[i]=;}dist[v]=infinite;for(i=1;ivertexNum;++i){intmin=infinite;intk=v;for(j=0;jvertexNum;++j)//在dist中查找最小值元素if(dist[j]min){k=j;min=dist[j];}cout从vertex[v]到vertex[k]的最短路径长度为dist[k]'\t';cout路程为path[k]endl;for(j=0;jvertexNum;++j)//更新dist数组和path数组的值if(dist[k]+arc[k][j]dist[j]){dist[j]=dist[k]+arc[k][j];path[j]=path[k]+-+vertex[j];//将其连接}dist[k]=infinite;//将该值标记为最大值，以便下次循环时忽略}}templateclassTvoidMGraphT::Floyd(){inti,j,t;for(i=0;ivertexNum;++i)//初始化矩阵dist和pathfor(j=0;jvertexNum;++j){length[i][j]=arc[i][j];if(length[i][j]!=infinite)path_Floyd[i][j]=vertex[i]+vertex[j];elsepath_Floyd[i][j]=;}for(t=0;tvertexNum;++t)//进行n次迭代for(i=0;ivertexNum;++i)//顶点i和j之间是否经过顶点kfor(j=0;jvertexNum;++j)if(length[i][j]length[i][t]+length[t][j]){length[i][j]=length[i][t]+length[t][j];path_Floyd[i][j]=path[i][t]+path_Floyd[t][j];}}templateclassTvoidMGraphT::Floyd_prinf(){inti,t;for(i=0;ivertexNum;++i)for(t=0;tvertexNum;++t)if(i!=t)//顶点自身除外{cout从vertex[i]到vertex[t]的最短路径长度为length[i][t]endl;}}test.cpp(主函数测试文件)#includeiostreamusingnamespacestd;#includeMGraph.cppintinfinite=9999;intmain(){MGraphstringg1;g1.Dijkstra(0);//测试Dijkstra算法MGraphstringg2;g2.Floyd();//测试Floyd算法g2.Floyd_prinf();return0;}9.1.3总结（1）实验过程中遇到的三个有意义的错误。a.运行程序出现错误，如图1-1所示。图1-1错误代码如图1-2所示。多次检验，代码的算法逻辑没有错误，根据错误提示是指数据类型出现了不对应。图1-2结合图1-3和1-4可发现，path是字符型数组，而在图1-2中path数组进行了连接操作，如果要满足字符连接，则用于存储的数组需要时字符串型的。故产生错误。图1-3图1-4b.运行程序出现错误提示，如图2-1所示，编译器提示infinite已经在test.obj中被定义。图2-1此时，“intinfinite=9999”位于MGraph.cpp文件中。如图2-2所示。图2-2将“intinfinite=9999”移至test.cpp文件中。如图2-3所示。图2-3再次运行程序，如图2-4所示，没有错误提示。图2-4c.当程序无错误提示时，运行程序。得到如图3-1所示结果。结果错误，不符合预期结果。图3-1找到出错代码位置，如图3-2。在上方的红框中dist[v]被赋值0，而此时v=0。这导致在下方的红框中将通过if判断，执行if后面的操作。而实际上dist[0]不应该参与接下来得操作，实际操作应该从dist[1]开始。所以上方红框中的代码需要改为“dist[v]=infinite”即可。图3-2（2）实验过程使用的主要知识点。a.有向图的邻接矩阵存储结构算法；b.Dijkstr算法最短路径。c.Floyd算法最短路径；（3）实验中遇到的不理解或体会比较深的问题。a.Dijkstra算法的主要特点是以起始点为中心向外层扩展，直到扩展到终点为止，每次迭代时选择的下一个顶点是标记点之外距离远点最近的顶点。b.Floyd算法非常的优雅，而且清晰易懂，采用松弛技术，对邻接矩阵进行三层for循环操作，进而对在i和j之间的所有其他点进行松弛。这种算法结构紧凑，适合稠密图。c.印象最深的是在写Dijkstr算法的时候，里面用到了两层for循环，而我用的自增量是i和j。当我写执行语句的时候无意间将i写成j，j写成。之后运行程序，编译器没有提示错误，但结果是错的。由于i和j看起来太像，所以导致我查找错误的时候总是发现不了错误。当发现我把i和j搞混的时候才焕然大悟。因此，打算以后将i和j分开了用，写双层循环的时候可以用i和t做自增量。