迪杰斯特拉算法代码c语言
时间: 2023-12-10 09:32:49 浏览: 35
以下是迪杰斯特拉算法的C语言代码实现:
```
#include <stdio.h>
#define MAXSIZE 100
#define INFINITY 65535
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType vexs[MAXSIZE];
EdgeType arc[MAXSIZE][MAXSIZE];
int numVertexes, numEdges;
} MGraph;
void Dijkstra(MGraph G, int v0, int *dist, int *path) {
int i, j, k, min;
int final[MAXSIZE];
// 初始化
for (i = 0; i < G.numVertexes; i++) {
final[i] = 0;
dist[i] = G.arc[v0][i];
path[i] = -1;
}
final[v0] = 1;
dist[v0] = 0;
// 进行n-1次循环
for (i = 1; i < G.numVertexes; i++) {
min = INFINITY;
// 找到当前未确定的距离v0最近的顶点k
for (j = 0; j < G.numVertexes; j++) {
if (!final[j] && dist[j] < min) {
k = j;
min = dist[j];
}
}
final[k] = 1;
// 更新dist和path数组
for (j = 0; j < G.numVertexes; j++) {
if (!final[j] && min + G.arc[k][j] < dist[j]) {
dist[j] = min + G.arc[k][j];
path[j] = k;
}
}
}
}
int main() {
MGraph G;
int v0 = 0;
int dist[MAXSIZE], path[MAXSIZE];
CreateMGraph(&G);
Dijkstra(G, v0, dist, path);
// 输出最短路径
for (int i = 0; i < G.numVertexes; i++) {
if (i != v0) {
printf("v%d到v%d的最短路径长度为:%d,路径为:", v0, i, dist[i]);
int j = i;
while (path[j] != -1) {
printf("%d<-", j);
j = path[j];
}
printf("%d\n", j);
}
}
return 0;
}
```