- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
新版【数据结构算法】实验8 图的最短路径问题(附源代码).doc
天天快乐
浙江大学城市学院实验报告
课程名称 数据结构与算法
实验项目名称 实验八 图的最短路径问题
实验成绩 指导老师(签名 ) 日期
实验目的和要求
掌握图的最短路径概念。
理解并能实现求最短路径的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中。
测试数据如下:
0
0
1
2
3
5
4
4
8
2
3
10
7
6
5
9
6
15
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)
功能:输出邻接矩阵表示的有向带权图 (即输出图的每条边)
思路:按照一定的格式输出邻接矩阵
④ 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[]
您可能关注的文档
最近下载
- 20210402张红伟教学成果奖讲座.pdf VIP
- 铁路路基压实质量检测—地基系数K30检测.pptx
- 《城市轨道交通车站设备》章节练习题及答案(全).doc VIP
- 初级中学政治教师资格考试学科知识与教学能力2024年下半年自测试题及解答.docx VIP
- 1530-7 高思学校竞赛数学导引·五年级 正文.pdf
- 中外历史纲要上第17课 第二次世界大战及战后国际秩序的形成 精品教学设计.docx VIP
- 2024陕西西安工程大学管理和专技岗位招聘12人笔试备考题库及答案解析.docx
- 变压器主保护——差动保护设计.docx VIP
- 电除尘器一般故障分析.docx
- 2024年下半年教师资格考试初级中学政治学科知识与教学能力自测试卷及解答.docx VIP
文档评论(0)