资源描述：
《【数据结构算法】实验8_图的最短路径问题(附源代码)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验八图的最短路径问题实验成绩指导老师（签名）日期一.实验目的和要求1.掌握图的最短路径概念。2.理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。二.实验内容1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括：①初始化邻接矩阵表示的有向带权图voidInitMatrix(adjmatrixG);②建立邻接矩阵表示的有向带权图voidCreateMatrix(adjmatrixG,intn)（即通过输入图的每条边建立图的邻接矩阵）;③输出邻接矩阵表示的有向带权图voidPrintMatri
2、x(adjmatrixG,intn)（即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。2、编写求最短路径的DijKstra算法函数voidDijkstra(adjmatrixGA,intdist[],edgenode*path[],inti,intn)，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组path和dist中。编写打印输出从源点到每个顶点的最短路径及长度的函数voidPrintPath(intdist[],edgenode*path[],intn)。3、编写测试程序（即主函数），首先建立并输出有向带权图，然后
3、计算并输出从某顶点v0到其余各顶点的最短路径。要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件test9_2.cpp中。测试数据如下：1101235448231076596154、填写实验报告，实验报告文件取名为report8.doc。5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。三.函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路【结构说明】constintMaxVer
4、texNum=10;//图的最大顶点数constintMaxEdgeNum=100;//边数的最大值constintMaxValue=32767;//权值的无穷大表示typedefintadjmatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵typedefstructNode{intadjvex;structNode*next;}edgenode;//路径结点【函数说明】①voidInitMatrix(adjmatrix&G)功能：初始化邻接矩阵表示的有向带权图思路：将邻接矩阵中的所有权值设置为无穷大（MaxValue）②voidCreateMatr
5、ix(adjmatrix&G,intn)功能：建立邻接矩阵表示的有向带权图（即通过输入图的每条边建立图的邻接矩阵）思路：按照输入的顶点信息和权值信息，更新邻接矩阵内对应的值③voidPrintMatrix(adjmatrixG,intn)功能：输出邻接矩阵表示的有向带权图（即输出图的每条边）思路：按照一定的格式输出邻接矩阵11④voidDijkstra(adjmatrixGA,intdist[],edgenode*path[],inti,intn)功能：求最短路径的DijKstra算法函数思路：按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度
6、。设立一个集合S，用以保存已求得最短路径的终点，其初值为只有一个元素，即源点；一个数组dist[n]，其每个分量dist[j]保存从源点经过S集合中顶点最后到达顶点j的路径中最短路径的长度，其初值为从源点到每个终点的弧的权值（没弧则置为∞）；一个指针数组path[n]，path[j]指向一个单链表，保存相应于dist[j]的从源点到顶点j的最短路径（即顶点序列），初值为空。⑤voidPATH(edgenode*path[],inti,intj)功能：将path[i]的路径改为path[j]的路径+i思路：分为三个步骤：一，删除path[i]中原来保存的链表；二，将path[j]的路
7、径复制给path[i]；三，将j结点加入path[i]的路径中⑥voidPrintPath(intdist[],edgenode*path[],intn){功能：打印输出从源点到每个顶点的最短路径及长度的函数思路：按照一定的格式遍历输出从源点到每个顶点的最短路径及长度四.实验结果与分析包括运行结果截图等【测试数据】0123544823107659615顶点数：7输入弧的信息：尾顶点头顶点权值0181103512214102462553133573615659正确的邻接
