Rosetta Code

Dijkstra's algorithm: Difference between revisions

Page Discussion

Dijkstra's algorithm (view source)

Revision as of 22:38, 11 February 2016

601 bytes added ,  8 years ago
→‎{{header|C}}: do not store vertex index in the vertex
(→‎{{header|C}}: no longer that extra test case)
(→‎{{header|C}}: do not store vertex index in the vertex)
Line 367:
#include <stdlib.h>
#include <limits.h>
#include <stdarg.h>
 
typedef struct {
Line 374 ⟶ 375:
 
typedef struct {
edge_t **edgeedges;
int edge_lenedges_len;
int edge_sizeedges_size;
int hindex;▼
int dist;
int prev;
int visited;
int vindex;
▲ int hindex;
} vertex_t;
 
typedef struct {
vertex_t **vertexvertices;
int vertex_lenvertices_len;
int vertex_sizevertices_size;
} graph_t;
 
typedef struct {
vertex_tint **vertexvertices;
int len;
int size;
Line 397:
 
void add_vertex (graph_t *g, int i) {
if (g->vertex_sizevertices_size < i + 1) {
int size = g->vertex_sizevertices_size * 2 > i ? g->vertex_sizevertices_size * 2 : i + 4;
g->vertexvertices = realloc(g->vertexvertices, size * sizeof (vertex_t *));
for (int j = g->vertex_sizevertices_size; j < size; j++) {
g->vertexvertices[j] = NULL;
}
g->vertex_sizevertices_size = size;
}
if (!g->vertexvertices[i]) {
g->vertexvertices[i] = calloc(1, sizeof (vertex_t));
g->vertex[i]->vindex = ivertices_len++;
g->vertex_len++;▼
}
}
Line 417 ⟶ 416:
add_vertex(g, a);
add_vertex(g, b);
vertex_t *v = g->vertexvertices[a];
if (v->edge_lenedges_len >= v->edge_sizeedges_size) {
v->edge_sizeedges_size = v->edge_sizeedges_size ? v->edge_sizeedges_size * 2 : 4;
v->edgeedges = realloc(v->edgeedges, v->edge_sizeedges_size * sizeof (edge_t *));
}
edge_t *e = calloc(1, sizeof (edge_t));
e->vertex = b;
e->weight = w;
v->edgeedges[v->edge_lenedges_len++] = e;
}
 
void push_heapup_heap (heap_t *h, vertex_tgraph_t *vg, int i) {
intvertex_t i,*v j= g->vertices[i];
ifint j = (v->hindex) {;
int k = j i =/ v->hindex2;
ifwhile (kj ==> i1) {▼
vertex_t *vu = g->vertices[h->vertexvertices[1k]];▼
while (i > 1 &&if h->vertex[j](u->dist >< v->dist) {▼
k = jbreak;▼
h->vertexvertices[ij] = h->vertexvertices[jk];▼
▲ gu->vertex_len++hindex = j;
ij = k;▼
jk = jk / 2;▼
}
elseh->vertices[j] {= i;
v->hindex = ij;▼
}
 
void push_heap (heap_t *h, graph_t *g, int i) {
vertex_t *v = g->vertices[i];
if (!v->hindex) {
if (h->len + 1 >= h->size) {
h->size = h->size ? h->size * 2 : 4;
h->vertexvertices = realloc(h->vertexvertices, h->size * sizeof (vertex_t *int));
}
h->len++;
iv->hindex = h->len;
}
jup_heap(h, =g, i / 2);
▲ while (i > 1 && h->vertex[j]->dist > v->dist) {
▲ h->vertex[i] = h->vertex[j];
h->vertex[i]->hindex = i;
i = j;
▲ j = j / 2;
}
h->vertex[i] = v;
▲ v->hindex = i;
}
 
vertex_tint *pop_heapmin (heap_t *h, graph_t *g, int n, ...) {
ifva_list (!h->len) {args;
va_start(args, n);
return NULL;▼
int m = va_arg(args, int);
▲ int i =, j;
for (i = 0; i < n - k = j1; i++) 1;{▼
j = va_arg(args, int);
if (j > h->len)
} break;▼
vertex_t *v = g->vertices[h->vertices[m]];
vertex_t *u = g->vertices[h->vertices[j]];
if (j <= h->len && h->vertex[j]u->dist < h->vertex[k]v->dist) {▼
} m = j;▼
}
va_end(args);
▲ vertex_t *v = h->vertex[1];
▲ return NULLm;
h->vertex[1] = h->vertex[h->len];▼
}
h->len--;▼
 
void down_heap (heap_t *h, graph_t *g) {
int k = h->vertices[1];
int i = 1;
while (1) {
int kj = min(h, g, 3, i, 2 * i, 2 * i + 1);
intif (j = 2 *= i;)
▲ if (j <= h->len && h->vertex[j]->dist < h->vertex[k]->dist) {
▲ k = j;
▲ }
if (j + 1 <= h->len && h->vertex[j + 1]->dist < h->vertex[k]->dist) {
▲ k = j + 1;
▲ }
▲ if (k == i) {
break;
h->vertices[i] = h->vertices[j];
}
g->vertices[h->vertexvertices[i]]->hindex = h->vertex[k]i;
h->vertex[i]->hindex = ij;
▲ i = k;
}
h->vertexvertices[i] = h->vertex[h->len + 1]k;
hg->vertexvertices[ik]->hindex = i;
}
return v;▼
 
int pop_heap (heap_t *h, graph_t *g) {
int i = h->vertices[1];
▲ h->vertexvertices[1] = h->vertexvertices[h->len];
▲ h->len--;
down_heap(h, g);
▲ return vi;
}
 
Line 485 ⟶ 502:
a = a - 'a';
b = b - 'a';
for (i = 0; i < g->vertex_lenvertices_len; i++) {
vertex_t *v = g->vertexvertices[i];
v->dist = INT_MAX;
v->prev = 0;
v->visited = 0;
}
vertex_t *v = g->vertexvertices[a]->dist = 0;
▲ hv->vertex[i]dist = v0;
heap_t *h = calloc(1, sizeof (heap_t));
push_heap(h, g->vertex[, a]);
while (1h->len) {
vertex_t *vi = pop_heap(h, g);
if (!v || v->vindexi == b) {
break;
}v = g->vertices[i];
v->visited = 1;
for (j = 0; j < v->edge_lenedges_len; j++) {
edge_t *e = v->edgeedges[j];
vertex_t *u = g->vertexvertices[e->vertex];
if (!u->visited && v->dist + e->weight <= u->dist) {
u->prev = v->vindexi;
u->dist = v->dist + e->weight;
push_heap(h, ug, e->vertex);
}
}
Line 512 ⟶ 530:
}
 
void print_path (graph_t *g, int a, int i) {
ai = ai - 'a';
vertex_t *v = g->vertexvertices[ai], *u = v;
if (v->dist == INT_MAX) {
printf("no path\n");
return;
}
ifint (!i)j {= 1, k;
while printf("%d ", vu->dist); {
u = g->vertices[u->prev];
}
if (v->dist) { j++;
print_path(g, 'a' + v->prev, i + 1);▼
}
printf("%c",char '*a' += amalloc(j);
ifa[j (!i)- {1] = 'a' + i;
for (k = 0, u = v; k < j - 1; k++, u = g->vertices[u->prev]) {
printf("\n");
▲ print_path(g,a[j - k - 2] = 'a' + vu->prev, i + 1);
}
printf("%d %.*s\n", v->dist, j, a);
}
 
Line 543 ⟶ 562:
add_edge(g, 'e', 'f', 9);
dijkstra(g, 'a', 'e');
print_path(g, 'e', 0);
return 0;
}
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/209912"