wdg.c (1557B)
1 #include "wdg.h" 2 3 void wdg_init(wdg_t *g, const size_t n) { 4 g->n = n; 5 g->nbrs = malloc(n * sizeof(*(g->nbrs))); 6 g->weight = malloc(n * sizeof(*(g->weight))); 7 8 size_t i; 9 for (i = 0; i < n; i++) { 10 stack_u64_init(&g->nbrs[i]); 11 stack_u64_init(&g->weight[i]); 12 } 13 } 14 15 void wdg_clear(wdg_t *g) { 16 size_t i; 17 for (i = 0; i < g->n; i++) { 18 stack_u64_clear(&g->nbrs[i]); 19 stack_u64_clear(&g->nbrs[i]); 20 } 21 free(g->nbrs); 22 free(g->weight); 23 } 24 25 void wdg_add_edge(wdg_t *g, const size_t v, const size_t w, uint64_t weight) { 26 stack_u64_push(&g->nbrs[v], w); 27 stack_u64_push(&g->weight[v], weight); 28 } 29 30 uint64_t wdg_dijkstra(wdg_t *g, const size_t source, const size_t target) { 31 size_t i; 32 uint64_t dist[g->n]; 33 dist[source] = 0; 34 size_t prev[g->n]; 35 36 fheap_t q; 37 fheap_init(&q); 38 39 size_t vertices[g->n]; 40 fnode_t *qvertex[g->n]; 41 42 for (i = 0; i < g->n; i++) { 43 vertices[i] = i; 44 if (i != source) { 45 dist[i] = UINT64_MAX; 46 prev[i] = SIZE_MAX; 47 } 48 49 qvertex[i] = fheap_insert(&q, dist[i], &(vertices[i])); 50 } 51 52 void *up; 53 size_t u, v; 54 uint64_t alt; 55 while (q.n > 0) { 56 size_t value = fheap_extract_min(&up, &q); 57 u = *(size_t *)up; 58 if (u == target) 59 break; 60 if (value == UINT64_MAX) 61 break; 62 63 for (i = 0; i < (g->nbrs[u]).nmemb; i++) { 64 v = (g->nbrs[u]).data[i]; 65 alt = dist[u] + (g->weight[u]).data[i]; 66 if (alt < dist[v]) { 67 dist[v] = alt; 68 prev[v] = u; 69 fheap_decrease_value(&q, qvertex[v], alt); 70 } 71 } 72 } 73 74 return dist[target]; 75 }