-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathDijkstra.c
More file actions
94 lines (79 loc) · 1.96 KB
/
Dijkstra.c
File metadata and controls
94 lines (79 loc) · 1.96 KB
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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define INF 100000000
#define MAX_VERTICES 100
typedef struct GraphType {
int n;
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int distance[MAX_VERTICES];
int found[MAX_VERTICES];
int choose(int distance[], int n, int found[]) {
int min, minpos;
min = INT_MAX;
minpos = -1;
for (int i = 0; i < n; i++) {
if (distance[i] < min && !found[i]) {
min = distance[i];
minpos = i;
}
}
return minpos;
}
void printStatus(GraphType* g) {
static int step = 1;
printf("STEP %d: ", step++);
printf("distance: ");
for (int i = 0; i < g->n; i++) {
if (distance[i] == INF) {
printf(" * ");
}
else {
printf("%2d ", distance[i]);
}
}
printf("\n");
printf("found: ");
for (int i = 0; i < g->n; i++) {
printf("%2d ", found[i]);
}
printf("\n\n");
}
void dijkstra(GraphType* g, int start) {
for (int i = 0; i < g->n; i++) {
distance[i] = g->weight[start][i];
found[i] = false;
}
found[start] = true;
distance[start] = 0;
int u;
for (int i = 0; i < (g->n - 1); i++) {
printStatus(g);
u = choose(distance, g->n, found);
found[u] = true;
for (int w = 0; w < g->n; w++) {
if (!found[w]) {
if (distance[u] + g->weight[u][w] < distance[w]) {
distance[w] = distance[u] + g->weight[u][w];
}
}
}
}
}
int main(void) {
GraphType g = { 7,
{
{ 0, 7, INF, INF, 3, 10, INF},
{ 7, 0, 4, 10, 2, 6, INF},
{ INF, 4, 0, 2, INF, INF, INF},
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5},
{ 10, 6, INF, 9, INF, 0, INF},
{ INF, INF, INF, 4, 5, INF, 0}
}
};
dijkstra(&g, 0);
return 0;
}