一、实验目的
讲清楚进行本实验后要学到的知识、掌握的数据结构及其定义和表示方法，讲清楚所采用的算法。
掌握图结构的（邻接矩阵）输入方法
掌握图结构的说明、创建以及图的存储表示（邻接矩阵）
掌握最短路径算法原理
掌握最短路径算法的编程实现方法
二、实验要求
讲清楚进行本实验之前需要的先验知识及条件
熟悉C++语言编程
熟悉图的邻接矩阵存储表示
熟悉最短路径算法原理
熟悉使用C++语言，实现最短路径算法
先验知识：
迪杰特斯拉算法思想：
设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一章为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中。直到全部顶点都加入到S中，算法就结束了）。第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点V到S中各顶点的最短路径长度大于从源点V到V中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从V到此顶点的最短路径长度，V中的顶点的距离是从V到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
三、实验内容
讲清楚本实验的内容，以及为实现实验内容所采用算法的原理
四、实验步骤
五、完整代码（可直接run） （编译环境vscode）
#include<stdio.h>
#define MAXVERTEXNUM 100 //定义数组长度
#define INFINITY 100//定义无穷
struct Graph{
int VertexNum;//图中顶点个数
char Vertex[MAXVERTEXNUM];//将图的顶点字母存入数组
int AdjMatrix[MAXVERTEXNUM][MAXVERTEXNUM];//设置领接矩阵用两个数组
};
Graph MGraph;
char Path[MAXVERTEXNUM][MAXVERTEXNUM];//设置图的邻接矩阵
int Dest[MAXVERTEXNUM];//全局设置权值
void CreateGraph(Graph *G);//生成图调用函数
void ShowGraph(Graph *G);//展示图调用函数
void ShortestPath(Graph *G, char StartVexChar);//测试路径
void ShowPath(Graph *G); //展示路径
int main(){
char StartVex;//
CreateGraph(&MGraph);
ShowGraph(&MGraph);
printf("请输入开始的顶点");
scanf("%c", &StartVex);
ShortestPath(&MGraph, StartVex);
ShowPath(&MGraph);
return 0;
}文章来源地址https://www.toymoban.com/news/detail-457063.html
//
void CreateGraph(Graph *G){
int i, j;
printf("请输入顶点个数\n");
scanf("%d", &G->VertexNum);
printf("请输入顶点\n");
getchar();
for(i = 1; i <= G->VertexNum; i++){
scanf("%c", &G->Vertex[i]);
getchar();
}文章来源：https://www.toymoban.com/news/detail-457063.html
printf("请输入邻接矩阵\n");
for(i = 1; i <= G->VertexNum; i++){
for(j = 1; j <= G->VertexNum; j++){
scanf("%d", &G->AdjMatrix[i][j]);
getchar();
if(G->AdjMatrix[i][j] == -1)
G->AdjMatrix[i][j] = INFINITY;
}
}
}
void ShowGraph(Graph *G){
int i, j;
for(i = 1; i <= G->VertexNum; i++){
printf("%c ", G->Vertex[i]);
}
putchar('\n');
for(i = 1; i <= G->VertexNum; i++){
for(j = 1; j <= G->VertexNum; j++){
printf("%d ", G->AdjMatrix[i][j]);
}
putchar('\n');
}
}
void ShortestPath(Graph *G, char StartVexChar){
int i, j, m, StartVex, CurrentVex, MinDest, Final[MAXVERTEXNUM];
for (i = 1; i <= G->VertexNum; i++){
if(G->Vertex[i] == StartVexChar){
StartVex = i;
break;
}
}
for (i = 1; i <= G->VertexNum; i++){
Path[i][0] = 0;
Dest[i] = INFINITY;
if(G->AdjMatrix[StartVex][i] < INFINITY){
Dest[i] = G->AdjMatrix[StartVex][i];
Path[i][1] = G->Vertex[StartVex];
Path[i][2] = G->Vertex[i];
Path[i][0] = 2;
}
Final[i] = 'F';
}
Dest[StartVex] = 0;
Final[StartVex] = 'T';
for (i = 1; i <= G->VertexNum; i++){
MinDest = INFINITY;
for (j = 1; j <= G->VertexNum; j++){
if(Final[j] == 'F'){
if(Dest[j] < MinDest){
CurrentVex = j;
MinDest = Dest[j];
}
}
}
Final[CurrentVex] = 'T';
for (j = 1; j <= G->VertexNum; j++){
if((Final[j] == 'F') && (MinDest + G->AdjMatrix[CurrentVex][j]) < Dest[j]){
Dest[j] = MinDest + G->AdjMatrix[CurrentVex][j];
for(m = 0; m <= Path[CurrentVex][0]; m++)
Path[j][m] = Path[CurrentVex][m];
Path[j][0]++;
Path[j][Path[j][0]] = G->Vertex[j];
}
}
}
}
void ShowPath(Graph *G){
int i, j;
for(i= 1; i <= G->VertexNum; i++){
printf("%c(%d):", G->Vertex[i], Dest[i]);
if(Path[i][0] > 0){
for(j = 1; j <= Path[i][0]; j++){
printf(" %c", Path[i][j]);
}
}
printf("%c\n", Path[i][j]);
}
}
到了这里，关于图的最短路径 （数据结构实验报告）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
