没有合适的资源?快使用搜索试试~ 我知道了~
【数据结构算法】实验8图的最短路径问题(附源代码)[收集].pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 96 浏览量
2021-10-13
00:03:05
上传
评论
收藏 341KB PDF 举报
温馨提示
试读
11页
【数据结构算法】实验8图的最短路径问题(附源代码)[收集].pdf
资源推荐
资源详情
资源评论
1
浙江大学城市学院实验报告
课程名称 数据结构与算法
实验项目名称 实验八 图的最短路径问题
实验成绩 指导老师(签名 ) 日期
一. 实验目的和要求
1. 掌握图的最短路径概念。
2. 理解并能实现求最短路径的 DijKstra算法(用邻接矩阵表示图)。
二. 实验内容
1、编写用邻接矩阵表示 有向带权图 时图的基本操作的实现函数, 基本操作包括:
① 初始化邻接矩阵表示的有向带权图 void InitMatrix(adjmatrix G);
② 建立邻接矩阵表示的有向带权图 void CreateMatrix(adjmatrix G, int n)
(即通过输入图的每条边建立图的邻接矩阵) ;
③ 输出邻接矩阵表示的有向带权图 void 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、编写测试程序(即主函数),首先建立并输出有向带权图,然后计算并输出
从某顶点 v0 到其余各顶点的最短路径。
要求:把指针数组的基类型结构定义 edgenode 、求最短路径的 DijKstra 算法
函数、打印输出最短路径及长度的函数 PrintPath 以及主函数存放在文件
test9_2.cpp 中。
测试数据如下:
2
4、填写实验报告,实验报告文件取名为 report8.doc 。
5、上传实验报告文件 report8.doc 与源程序文件 test9_2.cpp 及
Graph2.h 到 Ftp 服务器上自己的文件夹下。
三. 函数的功能说明及算法思路
包括每个函数的功能说明,及一些重要函数的算法实现思路
【结构说明】
const int MaxVertexNum=10; // 图的最大顶点数
const int MaxEdgeNum=100; // 边数的最大值
const int MaxValue=32767; //权值的无穷大表示
typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
typedef struct Node {
int adjvex;
struct Node *next;
} edgenode; //路径结点
【函数说明】
① void InitMatrix(adjmatrix &G)
功能:初始化邻接矩阵表示的有向带权图
思路:将邻接矩阵中的所有权值设置为无穷大( MaxValue)
② void CreateMatrix(adjmatrix &G, int n)
功能:建立邻接矩阵表示的有向带权图 (即通过输入图的每条边建立图的邻接矩
阵)
思路:按照输入的顶点信息和权值信息,更新邻接矩阵内对应的值
③ void PrintMatrix(adjmatrix G, int n)
功能:输出邻接矩阵表示的有向带权图 (即输出图的每条边)
思路:按照一定的格式输出邻接矩阵
0
1
2
3
5 4
4
8
2
3
10 7
6 5
9
6
15
3
④ void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n)
功能:求最短路径的 DijKstra 算法函数
思路:按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到
每个顶点的最短路径及长度。 设立一个集合 S,用以保存已求得最短路径的终点,
其初值为只有一个元素,即源点;一个数组 dist[n],其每个分量 dist[j] 保存从
源点经过 S集合中顶点最后到达顶点 j 的路径中最短路径的长度,其初值为从
源点到每个终点的弧的权值(没弧则置为∞);一个指针数组 path[n] ,path[j]
指向一个单链表,保存相应于 dist[j] 的从源点到顶点 j 的最短路径(即顶点序
列),初值为空。
⑤ void PATH(edgenode *path[], int i, int j)
功能:将 path[i] 的路径改为 path[j] 的路径 +i
思路:分为三个步骤:一,删除 path[i]中原来保存的链表;二,将 path[j] 的路径
复制给 path[i] ;三,将 j 结点加入 path[i] 的路径中
⑥ 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
剩余10页未读,继续阅读
资源评论
cyh76339129
- 粉丝: 1
- 资源: 14万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功