《2022年数据结构算法实验图的最短路径问题知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构算法实验图的最短路径问题知识 .pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验八图的最短路径问题实验成绩指导老师（签名）日期一. 实验目的和要求1.掌握图的最短路径概念。2.理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。二. 实验内容1、 编写用邻接矩阵表示 有向带权图 时图的基本操作的实现函数， 基本操作包括： 初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrix G); 建立邻接矩阵表示的有向带权图void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）; 输出邻接矩阵表示的有向带权图void
2、PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。2、编写求最短路径的DijKstra算法函数void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n) ，该算法求从顶点i 到其余顶点的最短路径与最短路径长度，并分别存于数组path 和 dist 中。 编写打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist, edgenode *path, int n)。3、编写测试程
3、序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点 v0 到其余各顶点的最短路径。要求：把指针数组的基类型结构定义edgenode 、求最短路径的 DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件test9_2.cpp中。测试数据如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2 4、填写实验报告，实验报告文件取名为report8.doc。5、上传实验报告文件re
4、port8.doc与源程序文件 test9_2.cpp及Graph2.h到 Ftp 服务器上自己的文件夹下。三. 函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路【结构说明】const int MaxVertexNum=10; /图的最大顶点数const int MaxEdgeNum=100; / 边数的最大值const int MaxValue=32767; /权值的无穷大表示typedef int adjmatrixMaxVertexNumMaxVertexNum; / 邻接矩阵typedef struct Node int adjvex; struct Nod
5、e *next; edgenode; /路径结点【函数说明】 void InitMatrix(adjmatrix &G) 功能：初始化邻接矩阵表示的有向带权图思路：将邻接矩阵中的所有权值设置为无穷大（MaxValue） void CreateMatrix(adjmatrix &G, int n) 功能：建立邻接矩阵表示的有向带权图 （即通过输入图的每条边建立图的邻接矩阵）思路：按照输入的顶点信息和权值信息，更新邻接矩阵内对应的值 void PrintMatrix(adjmatrix G, int n) 功能：输出邻接矩阵表示的有向带权图（即输出图的每条边）思路：按照一定的格式输出邻接矩阵0 1
6、 2 3 5 4 4 8 2 3 10 7 6 5 9 6 15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 3 void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n) 功能：求最短路径的DijKstra 算法函数思路：按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度。 设立一个集合 S， 用以保存已求
7、得最短路径的终点，其初值为只有一个元素，即源点；一个数组distn，其每个分量distj 保存从源点经过 S集合中顶点最后到达顶点j 的路径中最短路径的长度，其初值为从源点到每个终点的弧的权值（没弧则置为）；一个指针数组pathn，pathj指向一个单链表，保存相应于distj的从源点到顶点j 的最短路径（即顶点序列），初值为空。 void PATH(edgenode *path, int i, int j) 功能：将 pathi的路径改为 pathj 的路径 +i 思路：分为三个步骤：一，删除pathi中原来保存的链表；二，将pathj 的路径复制给 pathi；三，将 j 结点加入 pat
8、hi的路径中 void PrintPath(int dist, edgenode *path, int n) 功能：打印输出从源点到每个顶点的最短路径及长度的函数思路：按照一定的格式遍历输出从源点到每个顶点的最短路径及长度四. 实验结果与分析包括运行结果截图等【测试数据】顶点数： 7 输入弧的信息：尾顶点头顶点权值0 1 8 0 1 2 3 5 4 4 8 2 3 10 7 6 5 9 6 15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - -
9、 - - - - 4 0 3 5 1 2 2 1 4 10 2 4 6 2 5 5 3 1 3 3 5 7 3 6 15 6 5 9 正确的邻接矩阵应为：8 4 2 10 6 5 3 7 15 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 5 下面以测试数据为基准，给出DijKstra 算法生成最短路径的状态变化图：（注：顶点旁边的 代表当前状态下从源点到该顶点的最短路径长度）【状态】【状态】【状态】【状态】【状态】【状
10、态】0 1 2 3 5 4 4 2 3 7 6 6 15 0 1 2 3 5 4 4 2 3 7 6 6 15 0 1 2 3 5 4 4 2 3 7 6 6 15 0 1 2 3 5 4 4 2 3 10 7 6 15 0 1 2 3 5 4 4 3 7 6 15 0 1 2 3 5 4 4 8 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 6 【状态 (最短路径 )】五. 心得体会0 1 2 3 5 4 4 2 3
11、7 6 6 15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 7 记录实验感受、 上机过程中遇到的困难及解决办法、遗留的问题、 意见和建议等。【附录 -源程序】Test9_2.cpp #include #include #include #include #includeGraph2.h typedef struct Node int adjvex; struct Node *next; edgenode; void ma
12、in() int n; adjmatrix G; edgenode *pathMaxVertexNum; int distMaxVertexNum; void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n); void PrintPath(int dist, edgenode *path, int n); InitMatrix(G); printf(输入要构造的图顶点数 n); scanf(%d,&n); CreateMatrix(G,n); PrintMatrix(G,n); /打印图的邻接矩阵coutendle
13、ndl*以下为 DijKstra算法部分*endlendl; Dijkstra(G, dist, path, 0, n); PrintPath(dist,path,n); / 求最短路径的 DijKstra算法函数void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n) int j,k; int v = 1,minIndex; void PATH(edgenode *path, int i, int j); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -
14、 - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 8 bool *isStepped; / 初始化部分/isStepped：申请 n 个空间，除 i 以外均为 false /dist ：邻接矩阵中 i 顶点到各顶点的距离/path ：邻接矩阵中 i 顶点到各顶点若有路径，则保存；无路径置为NULL isStepped = new booln; for (j = 0; j adjvex = i; pathj-next = new edgenode; pathj-next-adjvex = j; pathj-next-next = NUL
15、L; else pathj = NULL; isSteppedj = false; isSteppedi = true; while(v = n) / 尝试查找当前最小路径结点，用minIndex保存顶点minIndex = i; for (k = 0; k n; k+) if (distk distminIndex & (!isSteppedk) minIndex = k; / 有查找到最小路径顶点，则将其并入集合if (minIndex != i) isSteppedminIndex = true; / 未查找到，则说明路径都为，退出else break; / 通过 while中确定的最小
16、路径顶点（minIndex ）到达当前顶点/ 若路径长度小于dist中保存的路径长度，则修改for (k = 0; k n; k+) if (GAminIndexk + distminIndex next; delete pathi; pathi = p; / 将 pathj的路径复制给 pathi p = new edgenode; p-adjvex = pathj-adjvex; pathi = p; t = pathj-next; while (t != NULL) q = p; p = new edgenode; p-adjvex = t-adjvex; q-next = p; t =
17、 t-next; / 将 j 结点加入 pathi的路径中q = p; p = new edgenode; p-adjvex = i; p-next = NULL; q-next = p; / 打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist, edgenode *path, int n) int i; edgenode *p; for (i = 1; i n; i+) cout vi endl; cout 最短路径： ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
18、- - - - - - - 第 9 页，共 11 页 - - - - - - - - - 10 p = pathi; if (p = NULL) cout 无路径！ endlendl; continue; while( p != NULL) coutvadjvexnext; coutendl 最短长度： distiendlendl; Graph2.h const int MaxVertexNum=10; / 图的最大顶点数const int MaxEdgeNum=100; / 边数的最大值const int MaxValue=32767; / 权值的无穷大表示typedef int adjma
19、trixMaxVertexNumMaxVertexNum; / 邻接矩阵/ 初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrix &G) int i,j; for (i=0; iMaxVertexNum; i+) / 邻接矩阵初始化for (j=0; j头顶点名，权值输入数据，以 0-0,0结尾:如A-B,23 n); while(true) / 构造邻接矩阵scanf(%d-%d,%d,&v,&w,&q); / 输入弧的两个定点及该弧的权重getchar(); if (v = 0 & w = 0 ) break; if( v = n | w = n) cerrve
20、rtex ERROR!;exit(1); Gvw=q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 11 / 输出邻接矩阵表示的有向带权图（即输出图的每条边）void PrintMatrix(adjmatrix G, int n) int i,j; coutendl-endl; coutYour Graph is:endlendl; for (i=0; in; i+) for (j=0; jn; j+) if(Gij!=MaxValue) printf( %2d | ,Gij); else printf( | ); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -