数据结构实验-图-求最短路径
需积分: 5 97 浏览量
2023-01-12
12:38:52
上传
评论
收藏 1.2MB DOCX 举报
1 / 8
数据结构实验报告
学号： 姓名： 专业：
知识范畴：图 完成日期：
实验题目：求最短回路
课程目标 1（3 分）
课程目标 2（2 分）
批阅人签字
程序代码及测试
写作、排版、代码注释等
总分(5 分)
实验内容及要求：
用字符文件提供数据建立带权网络存储结构。编写程序，输出该图中的最短回路（包括回
路上的顶点序列以及回路的长度）。提示：用迪杰特斯拉算法或弗洛依德算法求出所有结点自
已到自己的最短路径，选出其中的最小值即为该图的最短回路。
实验目的：掌握图的存储结构；掌握图的最短路径算法。
数据结构设计简要描述：
建立 Graph 结构体，包含图的顶点，边数，图的顶点以及邻接矩阵。
算法设计简要描述：
建立图，构造图的邻接矩阵。
用迪杰特斯拉算法求最短路径。
迪杰特斯拉算法：
有两个集合 S，U。S 的作用是记录已求出最短路径的顶点（以及相应的路径长度），而 U
中记录还未求出最短路径的顶点(以及该顶点到起点 s 的距离)。
初始时，S 中只有起点 s；U 中是除 s 之外的顶点，并且 U 中顶点的路径是"起点 s 到该顶
点的路径"。然后，从 U 中找出路径最短的顶点，并将其加入到 S 中；接着，更新 U 中的顶点
和顶点对应的路径。 然后，再从 U 中找出路径最短的顶点，并将其加入到 S 中；接着，更新 U
中的顶点和顶点对应的路径。重复该操作，直到遍历完所有顶点。
求无向图最短回路：
1. 用迪杰特斯拉算法求 vi 到其他点(vj)的最短距离 dist[vj]（排除直接两点直接相连
那条路径）
2. 求出点 vi 到自身的距离最短的环路，比较 dist[vj]+G.arcs[vi][vj]
3. 对每个点重复上述步骤，找到最短的回路
主函数调用 Dijkstra 函数依次求各个顶点自己到自己的最短路径，最小回路长度存储在
mindist 中，最短回路上的顶点序列存在 minpath 中。
输入/输出设计简要描述：
输入：用 fstream 从字符文件中读入数据
资源评论
