数据结构系列24 - 最短路径dijkstra算法 - C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h>
#include <stdlib.h>

#define MAX 32767

typedef struct Graph {
char* vexs;
int** arcs;
int vexNum;
int arcNum;
}Graph;

Graph* initGraph(int vexNum) {
Graph* G = (Graph*)malloc(sizeof(Graph));
G -> vexs = (char*)malloc(sizeof(char) * vexNum);
G -> arcs = (int**)malloc(sizeof(int*) * vexNum);
for (int i = 0 ; i < vexNum; i++) {
G -> arcs[i] = (int*)malloc(sizeof(int) * vexNum);
}
G -> vexNum = vexNum;
G -> arcNum = 0;
return G;
}

void createGraph(Graph* G, char* vexs, int* arcs) {
for (int i = 0 ; i < G -> vexNum; i++) {
G -> vexs[i] = vexs[i];
for (int j = 0; j < G -> vexNum; j++) {
G -> arcs[i][j] = *(arcs + i * G -> vexNum + j);
if (G -> arcs[i][j] != 0 && G -> arcs[i][j] != MAX)
G -> arcNum ++;
}
}
G -> arcNum /= 2;
}

void DFS(Graph* G, int* visited, int index) {
printf("%c\t", G -> vexs[index]);
visited[index] = 1;
for (int i = 0; i < G ->vexNum; i++) {
if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX && !visited[i]) {
DFS(G, visited, i);
}
}
}

int getMin(int* d, int* s, Graph* G) {
int min = MAX;
int index;
for (int i = 0; i < G -> vexNum; i++) {
if (!s[i] && d[i] < min) {
min = d[i];
index = i;
}
}
return index;
}

void dijkstra(Graph* G, int index) {
// 准备辅助数组
int* s = (int*)malloc(sizeof(int) * G -> vexNum);
int* p = (int*)malloc(sizeof(int) * G -> vexNum);
int* d = (int*)malloc(sizeof(int) * G -> vexNum);
// 初始化辅助数组
for (int i = 0; i < G -> vexNum; i++) {
if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX) {
d[i] = G -> arcs[index][i];
p[i] = index;
}
else {
d[i] = MAX;
p[i] = -1;
}
if (i == index) {
s[i] = 1;
d[i] = 0;
}
else
s[i] = 0;
}
for (int i = 0; i < G -> vexNum - 1; i++) {
int index = getMin(d, s, G);
s[index] = 1;
for (int j = 0; j < G -> vexNum; j++) {
if (!s[j] && d[index] + G -> arcs[index][j] < d[j]) {
d[j] = d[index] + G -> arcs[index][j];
p[j] = index;
}
}
}
for (int i = 0; i < G ->vexNum; i++) {
printf("%d %d %d\n", s[i], p[i], d[i]);
}
}

int main() {
Graph* G = initGraph(7);
int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
for (int i = 0; i < G -> vexNum; i++)
visited[i] = 0;
int arcs[7][7] = {
0, 12, MAX, MAX, MAX, 16, 14,
12, 0, 10, MAX, MAX, 7, MAX,
MAX, 10, 0, 3, 5, 6, MAX,
MAX, MAX, 3, 0, 4, MAX, MAX,
MAX, MAX, 5, 4, 0, 2, 8,
16, 7, 6, MAX, 2, 0, 9,
14, MAX, MAX, MAX, 8, 9, 0
};
createGraph(G, "1234567", (int*)arcs);
DFS(G, visited, 0);
printf("\n");
dijkstra(G, 0);
return 0;
}