Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|C}}: Make the heap functions unaware of the graph
(→{{header|C}}: do not store vertex index in the vertex) |
(→{{header|C}}: Make the heap functions unaware of the graph) |
||
Line 362:
=={{header|C}}==
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct {
Line 378 ⟶ 377:
int edges_len;
int edges_size;
int hindex;▼
int dist;
int prev;
Line 391 ⟶ 389:
typedef struct {
int *
int len;
int size;
Line 400:
int size = g->vertices_size * 2 > i ? g->vertices_size * 2 : i + 4;
g->vertices = realloc(g->vertices, size * sizeof (vertex_t *));
for (int j = g->vertices_size; j < size; j++)
g->vertices[j] = NULL;
}▼
g->vertices_size = size;
}
Line 427 ⟶ 426:
}
h->data = calloc(n + 1, sizeof (int));
int j = v->hindex;▼
vertex_t *u = g->vertices[h->vertices[k]];▼
break;▼
u->hindex = j;▼
j = k;▼
h->vertices[j] = i;▼
}
void push_heap (heap_t *h,
while (i
if
▲ break;
h->
}
}
int min (heap_t *h,
if (j <= h->len && h->prio[j] < h->prio[m])
if (k <= h->len && h->prio[k] < h->prio[m])
▲ int i, j;
vertex_t *u = g->vertices[h->vertices[j]];▼
return m;
}
int
h->prio[1] = h->prio[h->len];
h->index[h->data[1]] = 1;
h->len--;▼
int i = 1;
while (1) {
int j = min(h
if (j == i)
break;
h->
h->index[h->data[i]] = i;
i = j;
}
h->
h->index[h->data[i]] = i;
return v;
▲ h->vertices[1] = h->vertices[h->len];
▲ h->len--;
▲ return i;
}
Line 510 ⟶ 494:
vertex_t *v = g->vertices[a];
v->dist = 0;
heap_t *h =
push_heap(h,
while (h->len) {
i = pop_heap(h
if (i == b)
break;
Line 524 ⟶ 508:
u->prev = i;
u->dist = v->dist + e->weight;
push_heap(h
}
}
Line 531 ⟶ 515:
void print_path (graph_t *g, int i) {
vertex_t *v, *u;
i = i - 'a';
if (v->dist == INT_MAX) {
printf("no path\n");
return;
}
char
path[n - 1] = 'a'
▲ a[j - k - 2] = 'a' + u->prev;
▲ printf("%d %.*s\n", v->dist, j, a);
}
Line 564 ⟶ 546:
print_path(g, 'e');
return 0;
}</lang>▼
▲</lang>
output<pre>26 acde
| |||