讲解下面的代码 //最短路径—— Dijiksra //邻接矩阵 无向图 #include<stdio.h> #include<stdlib.h> #define Max 1001 #define MaxSize 100 //1)图的数据类型 typedef struct { int vertex[MaxSize];//存储点的信息 int edge[MaxSize][MaxSize];//存储便之间的邻接关系 int vertexNum,edgeNum;//点的个数,边的个数 }MGraph; //2)构造一个图 MGraph CreatGraph(int n,int m) { MGraph G; int i,j,a,b,c; //点 边 G.vertexNum=n; G.edgeNum=m; //点的信息 for(i=1;i<=G.vertexNum;i++) { G.vertex[i]=i; } //边邻接关系的初始化 for(i=1;i<=G.vertexNum;i++) { for(j=1;j<=G.vertexNum;j++) { if(i==j) { G.edge[i][j]=0; } else { G.edge[i][j]=Max; } } } //输入m行边的信息 for(i=1;i<=G.edgeNum;i++) { scanf("%d %d %d",&a,&b,&c); G.edge[a][b]=c; G.edge[b][a]=c;//无向图 } return G; } //3)核心算法 void Dijkstra(MGraph G, int v,int n)/*从源点v出发*/ { int i, k, num, dist[n],d[n]; //初始化 for (i = 2; i <=G.vertexNum; i++) { dist[i] = G.edge[v][i];//存储当前最短路径的长度 } for (num = 1; num < G.vertexNum; num++) { for (k = 2, i = 2; i <=G.vertexNum; i++) { if(dist[k]==0) { for(k=2;k<=G.vertexNum;k++) { if((dist[k]==0)&&(dist[k+1]!=0)) { k++; break; } } } if ((dist[i] != 0) && (dist[i] < dist[k])) { k = i; } } for (i = 2; i <=G.vertexNum; i++) { if (dist[i] > dist[k] + G.edge[k][i]) { dist[i] = dist[k] + G.edge[k][i]; } } d[k]=dist[k]; dist[k] = 0; } printf("%d",d[G.vertexNum]); } int main() { int n,m;//场所,边 scanf("%d %d",&n,&m); //创造 MGraph G; G=CreatGraph(n,m); //Dijksra int v; v=1; Dijkstra(G,v,n); return 0; }
时间: 2024-01-27 16:06:05 浏览: 25
这段代码实现了Dijkstra算法求无向图中的最短路径。下面是详细解释:
1.定义图的数据类型
定义了一个结构体MGraph,包含了存储点的信息和便之间的邻接关系,以及点的个数和边的个数。
2.构造一个图
CreatGraph函数用来构造一个无向图,通过输入点和边的信息来初始化邻接矩阵。其中,点的信息是顺序排列的,边的邻接关系初始化为最大值Max,表示不相邻。
3.核心算法
Dijkstra函数实现了Dijkstra算法,用来求从源点v到其它点的最短路径。首先,初始化dist数组,表示从源点v到其它点的当前最短路径的长度。然后,通过循环找到当前dist数组中最小的元素,设其下标为k,将其加入d数组中,并将其dist值设为0,表示已经找到了最短路径。接下来,更新dist数组,如果从源点v到点i的路径经过点k比当前的最短路径更短,则更新dist[i]的值。重复以上步骤,直到所有点都加入d数组中,此时d[G.vertexNum]的值即为从源点v到终点n的最短路径长度。
4.主函数
主函数中,先输入点和边的个数,构造一个图,然后调用Dijkstra函数求最短路径,并输出结果。
相关问题
#include <stdio.h> #include <stdlib.h> struct ENode { int adjVex; int w; struct ENode* nextArc; }; struct Node { struct ENode* firstArc; struct Node* preNode; //前驱节点指针 }; struct ENode** a; //
这段代码是定义了一个邻接表表示图的结构体。其中,ENode结构体表示边,包含邻接点编号和边权值,用于表示从一个节点到另一个节点的连边信息。Node结构体表示节点,包含指向第一条边的指针和指向前驱节点的指针,用于表示节点之间的相邻关系。
a是一个指向指针的指针,用于存储邻接表,它的大小为节点个数,每个元素指向一个链表,表示该节点的出边信息。这个邻接表可以用于表示有向图和无向图。
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <crtdbg.h>//add this header file to detect memory leaks #define MAXVER 5 #define true 1 #define false 0 //权重类型,此处为int typedef int DataType; typedef DataType DistanceMatrix; typedef struct { _Bool _visit; DataType _value; }MyVertex; typedef MyVertex ShortPathTable; typedef struct { int _vernum; DataType _matrix[MAXVER][MAXVER]; }MyGraph; void CreateGraph(MyGraph* G, DataType(*MyMatrix)[MAXVER]); void Dijkstra(MyGraph* G,int v,ShortPathTable* D); void FloydWarshall(MyGraph* G, DistanceMatrix(*D)[MAXVER]);根据头文件补全函数
好的,根据这个头文件,需要补全三个函数的代码实现,分别是CreateGraph、Dijkstra和FloydWarshall。
1. CreateGraph函数:
```
void CreateGraph(MyGraph* G, DataType(*MyMatrix)[MAXVER]) {
assert(G != NULL && MyMatrix != NULL);
G->_vernum = MAXVER;
for (int i = 0; i < MAXVER; i++) {
for (int j = 0; j < MAXVER; j++) {
G->_matrix[i][j] = MyMatrix[i][j];
}
}
}
```
这个函数的作用是创建一个图,并初始化它的邻接矩阵。这里假设邻接矩阵已经被赋值给了MyMatrix数组,函数会把它复制到图的_matrix数组中。注意,这里的图是一个无向图,如果需要创建有向图,需要根据具体情况修改代码。
2. Dijkstra函数:
这个函数的代码实现已经在之前的回答中给出了,可以直接使用。不过需要注意的是,这个函数中的MyGraph结构体中的_matrix数组是一个二维数组,用来存储图的邻接矩阵。如果要使用这个函数,需要先通过CreateGraph函数创建一个图,并把邻接矩阵存储在_matrix数组中。
3. FloydWarshall函数:
```
void FloydWarshall(MyGraph* G, DistanceMatrix(*D)[MAXVER]) {
assert(G != NULL && D != NULL);
int n = G->_vernum;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
(*D)[i][j] = G->_matrix[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((*D)[i][j] > (*D)[i][k] + (*D)[k][j]) {
(*D)[i][j] = (*D)[i][k] + (*D)[k][j];
}
}
}
}
}
```
这个函数实现了Floyd-Warshall算法,用来计算图中任意两个点之间的最短路径。和Dijkstra算法类似,这个函数也需要一个图的指针和一个距离矩阵的指针作为参数。函数会把邻接矩阵复制到距离矩阵中,并通过三重循环计算任意两个点之间的最短路径。这里的距离矩阵是一个二维数组,用来存储任意两个点之间的距离。