概述
一
.
实验目的和要求
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
中。
测试数据如下：
最后
以上就是外向心锁为你收集整理的数据结构最短路径例题_【数据结构算法】实验8 图的最短路径问题(附源代码)...的全部内容，希望文章能够帮你解决数据结构最短路径例题_【数据结构算法】实验8 图的最短路径问题(附源代码)...所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复