/
dijkstra.c
58 lines (47 loc) · 1.25 KB
/
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
#include "cplayground.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
const long INF = 1 << 30;
Edge *new_Edge(long dst, long cost) {
Edge *edge = xmalloc(sizeof(Edge));
edge->dst = dst;
edge->cost = cost;
return edge;
}
static int cmp_Edge(void *lhs, void *rhs) {
Edge *le = (Edge *)lhs;
Edge *re = (Edge *)rhs;
if (le->cost >= re->cost) {
return 1;
} else {
return -1;
}
}
Vector *dijkstra(Vector *tree, long src) {
size_t V = tree->len;
Vector *dist = new_vec_with(V);
for (size_t i = 0; i < V; i++) {
dist->data[i] = INT_TO_VoPTR(INF);
}
PriorityQueue *pqueue = new_PriorityQueue(cmp_Edge);
dist->data[src] = 0;
pqueue_push(pqueue, new_Edge(src, 0));
while (!pqueue_empty(pqueue)) {
Edge *e = pqueue_pop(pqueue);
long v = e->dst, cost = e->cost;
if (VoPTR_TO_INT(dist->data[v]) < cost) {
continue;
}
Vector *vec = tree->data[v];
VecForeachWithType(vec, Edge *, e, {
if (VoPTR_TO_INT(dist->data[v]) + e->cost <
VoPTR_TO_INT(dist->data[e->dst])) {
dist->data[e->dst] =
INT_TO_VoPTR(VoPTR_TO_INT(dist->data[v]) + e->cost);
pqueue_push(pqueue, new_Edge(e->dst, VoPTR_TO_INT(dist->data[e->dst])));
}
});
}
return dist;
}