Dijkstra's algorithm: Difference between revisions

Content added Content deleted
(→‎{{header|C}}: no longer that extra test case)
(→‎{{header|C}}: do not store vertex index in the vertex)
Line 367: Line 367:
#include <stdlib.h>
#include <stdlib.h>
#include <limits.h>
#include <limits.h>
#include <stdarg.h>


typedef struct {
typedef struct {
Line 374: Line 375:


typedef struct {
typedef struct {
edge_t **edge;
edge_t **edges;
int edge_len;
int edges_len;
int edge_size;
int edges_size;
⚫
int hindex;
int dist;
int dist;
int prev;
int prev;
int visited;
int visited;
int vindex;
⚫
int hindex;
} vertex_t;
} vertex_t;


typedef struct {
typedef struct {
vertex_t **vertex;
vertex_t **vertices;
int vertex_len;
int vertices_len;
int vertex_size;
int vertices_size;
} graph_t;
} graph_t;


typedef struct {
typedef struct {
vertex_t **vertex;
int *vertices;
int len;
int len;
int size;
int size;
Line 397: Line 397:


void add_vertex (graph_t *g, int i) {
void add_vertex (graph_t *g, int i) {
if (g->vertex_size < i + 1) {
if (g->vertices_size < i + 1) {
int size = g->vertex_size * 2 > i ? g->vertex_size * 2 : i + 4;
int size = g->vertices_size * 2 > i ? g->vertices_size * 2 : i + 4;
g->vertex = realloc(g->vertex, size * sizeof (vertex_t *));
g->vertices = realloc(g->vertices, size * sizeof (vertex_t *));
for (int j = g->vertex_size; j < size; j++) {
for (int j = g->vertices_size; j < size; j++) {
g->vertex[j] = NULL;
g->vertices[j] = NULL;
}
}
g->vertex_size = size;
g->vertices_size = size;
}
}
if (!g->vertex[i]) {
if (!g->vertices[i]) {
g->vertex[i] = calloc(1, sizeof (vertex_t));
g->vertices[i] = calloc(1, sizeof (vertex_t));
g->vertex[i]->vindex = i;
g->vertices_len++;
⚫
g->vertex_len++;
}
}
}
}
Line 417: Line 416:
add_vertex(g, a);
add_vertex(g, a);
add_vertex(g, b);
add_vertex(g, b);
vertex_t *v = g->vertex[a];
vertex_t *v = g->vertices[a];
if (v->edge_len >= v->edge_size) {
if (v->edges_len >= v->edges_size) {
v->edge_size = v->edge_size ? v->edge_size * 2 : 4;
v->edges_size = v->edges_size ? v->edges_size * 2 : 4;
v->edge = realloc(v->edge, v->edge_size * sizeof (edge_t *));
v->edges = realloc(v->edges, v->edges_size * sizeof (edge_t *));
}
}
edge_t *e = calloc(1, sizeof (edge_t));
edge_t *e = calloc(1, sizeof (edge_t));
e->vertex = b;
e->vertex = b;
e->weight = w;
e->weight = w;
v->edge[v->edge_len++] = e;
v->edges[v->edges_len++] = e;
}
}


void push_heap (heap_t *h, vertex_t *v) {
void up_heap (heap_t *h, graph_t *g, int i) {
int i, j;
vertex_t *v = g->vertices[i];
if (v->hindex) {
int j = v->hindex;
i = v->hindex;
int k = j / 2;
⚫
while (j > 1) {
⚫
vertex_t *u = g->vertices[h->vertices[k]];
⚫
if (u->dist < v->dist)
⚫
break;
⚫
h->vertices[j] = h->vertices[k];
⚫
u->hindex = j;
⚫
j = k;
⚫
k = k / 2;
}
}
else {
h->vertices[j] = i;
⚫
v->hindex = j;
}

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) {
if (h->len + 1 >= h->size) {
h->size = h->size ? h->size * 2 : 4;
h->size = h->size ? h->size * 2 : 4;
h->vertex = realloc(h->vertex, h->size * sizeof (vertex_t *));
h->vertices = realloc(h->vertices, h->size * sizeof (int));
}
}
h->len++;
h->len++;
i = h->len;
v->hindex = h->len;
}
}
j = i / 2;
up_heap(h, g, i);
⚫
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_t *pop_heap (heap_t *h) {
int min (heap_t *h, graph_t *g, int n, ...) {
if (!h->len) {
va_list args;
va_start(args, n);
⚫
return NULL;
int m = va_arg(args, int);
⚫
int i, j;
⚫
for (i = 0; i < n - 1; i++) {
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 (u->dist < v->dist)
⚫
m = j;
}
}
va_end(args);
⚫
vertex_t *v = h->vertex[1];
⚫
return m;
⚫
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;
int i = 1;
while (1) {
while (1) {
int k = i;
int j = min(h, g, 3, i, 2 * i, 2 * i + 1);
int j = 2 * i;
if (j == 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;
break;
h->vertices[i] = h->vertices[j];
}
h->vertex[i] = h->vertex[k];
g->vertices[h->vertices[i]]->hindex = i;
h->vertex[i]->hindex = i;
i = j;
⚫
i = k;
}
}
h->vertex[i] = h->vertex[h->len + 1];
h->vertices[i] = k;
h->vertex[i]->hindex = i;
g->vertices[k]->hindex = i;
}
⚫
return v;

int pop_heap (heap_t *h, graph_t *g) {
int i = h->vertices[1];
⚫
h->vertices[1] = h->vertices[h->len];
⚫
h->len--;
down_heap(h, g);
⚫
return i;
}
}


Line 485: Line 502:
a = a - 'a';
a = a - 'a';
b = b - 'a';
b = b - 'a';
for (i = 0; i < g->vertex_len; i++) {
for (i = 0; i < g->vertices_len; i++) {
vertex_t *v = g->vertex[i];
vertex_t *v = g->vertices[i];
v->dist = INT_MAX;
v->dist = INT_MAX;
v->prev = 0;
v->prev = 0;
v->visited = 0;
v->visited = 0;
}
}
g->vertex[a]->dist = 0;
vertex_t *v = g->vertices[a];
⚫
v->dist = 0;
heap_t *h = calloc(1, sizeof (heap_t));
heap_t *h = calloc(1, sizeof (heap_t));
push_heap(h, g->vertex[a]);
push_heap(h, g, a);
while (1) {
while (h->len) {
vertex_t *v = pop_heap(h);
i = pop_heap(h, g);
if (!v || v->vindex == b) {
if (i == b)
break;
break;
}
v = g->vertices[i];
v->visited = 1;
v->visited = 1;
for (j = 0; j < v->edge_len; j++) {
for (j = 0; j < v->edges_len; j++) {
edge_t *e = v->edge[j];
edge_t *e = v->edges[j];
vertex_t *u = g->vertex[e->vertex];
vertex_t *u = g->vertices[e->vertex];
if (!u->visited && v->dist + e->weight <= u->dist) {
if (!u->visited && v->dist + e->weight <= u->dist) {
u->prev = v->vindex;
u->prev = i;
u->dist = v->dist + e->weight;
u->dist = v->dist + e->weight;
push_heap(h, u);
push_heap(h, g, e->vertex);
}
}
}
}
Line 512: Line 530:
}
}


void print_path (graph_t *g, int a, int i) {
void print_path (graph_t *g, int i) {
a = a - 'a';
i = i - 'a';
vertex_t *v = g->vertex[a];
vertex_t *v = g->vertices[i], *u = v;
if (v->dist == INT_MAX) {
if (v->dist == INT_MAX) {
printf("no path\n");
printf("no path\n");
return;
return;
}
}
if (!i) {
int j = 1, k;
printf("%d ", v->dist);
while (u->dist) {
u = g->vertices[u->prev];
}
if (v->dist) {
j++;
⚫
print_path(g, 'a' + v->prev, i + 1);
}
}
printf("%c", 'a' + a);
char *a = malloc(j);
if (!i) {
a[j - 1] = 'a' + i;
for (k = 0, u = v; k < j - 1; k++, u = g->vertices[u->prev]) {
printf("\n");
⚫
a[j - k - 2] = 'a' + u->prev;
}
}
printf("%d %.*s\n", v->dist, j, a);
}
}


Line 543: Line 562:
add_edge(g, 'e', 'f', 9);
add_edge(g, 'e', 'f', 9);
dijkstra(g, 'a', 'e');
dijkstra(g, 'a', 'e');
print_path(g, 'e', 0);
print_path(g, 'e');
return 0;
return 0;
}
}
Retrieved from "https://rosettacode.org/wiki/Dijkstra%27s_algorithm"