Dijkstra's algorithm: Difference between revisions

Content added Content deleted
m (→‎{{header|C}}: unused vars)
(→‎{{header|C}}: buthered the program so it runs faster for large graph)
Line 58: Line 58:
#include <stdlib.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>

⚫
//#define BIG_EXAMPLE


typedef struct node_t node_t, *heap_t;
typedef struct node_t node_t, *heap_t;
typedef struct edge_t edge_t;
typedef struct edge_t edge_t;
struct edge_t {
struct edge_t {
node_t *nd;
node_t *nd; /* target of this edge */
edge_t *sibling;
edge_t *sibling;/* for singly linked list */
int len;
int len; /* edge cost */
};
};
struct node_t {
struct node_t {
edge_t *edge; /* singly linked list of edges */
edge_t *edge; /* singly linked list of edges */
node_t *via; /* where previous node is in shortest path */
node_t *via; /* where previous node is in shortest path */
double dist;
double dist; /* distance from origining node */
char name[8];
char name[8]; /* the, er, name */
int heap_idx; /* link to heap position for updating distance */
int heap_idx; /* link to heap position for updating distance */
};
};



/* --- edge management --- */
#ifdef BIG_EXAMPLE
# define BLOCK_SIZE (1024 * 32 - 1)
#else
# define BLOCK_SIZE 15
#endif
edge_t *edge_root = 0, *e_next = 0;

/* Don't mind the memory management stuff, they are besides the point.
⚫
Pretend e_next = malloc(sizeof(edge_t)) */
⚫
void add_edge(node_t *a, node_t *b, double d)
⚫
{
if (e_next == edge_root) {
edge_root = malloc(sizeof(edge_t) * (BLOCK_SIZE + 1));
edge_root[BLOCK_SIZE].sibling = e_next;
e_next = edge_root + BLOCK_SIZE;
⚫
}
--e_next;

⚫
e_next->nd = b;
⚫
e_next->len = d;
⚫
e_next->sibling = a->edge;
⚫
a->edge = e_next;
⚫
}

⚫
void free_edges()
⚫
{
for (; edge_root; edge_root = e_next) {
e_next = edge_root[BLOCK_SIZE].sibling;
⚫
free(edge_root);
⚫
}
}

/* --- priority queue stuff --- */
heap_t *heap;
heap_t *heap;
int heap_len;
int heap_len;
Line 84: Line 121:
if (nd->via && d >= nd->dist) return;
if (nd->via && d >= nd->dist) return;


/* find existing or create new heap enntry */
/* find existing heap entry, or create a new one */
nd->dist = d;
nd->dist = d;
nd->via = via;
nd->via = via;


if (!(i = nd->heap_idx))
i = nd->heap_idx;
i = ++heap_len;
if (!i) i = ++heap_len;


/* upheap */
/* upheap */
Line 123: Line 160:
}
}


/* --- Dijkstra stuff; unreachable nodes will never make into the queue --- */
⚫
void add_edge(node_t *a, node_t *b, double d)
⚫
{
⚫
edge_t *e = malloc(sizeof(edge_t));
⚫
e->nd = b;
⚫
e->len = d;
⚫
e->sibling = a->edge;
⚫
a->edge = e;
⚫
}

void calc_all(node_t *start)
void calc_all(node_t *start)
{
{
Line 155: Line 184:
}
}


⚫
void free_edges(node_t *nd)
⚫
{
edge_t *e, *tmp;
for (e = nd->edge; e; e = tmp) {
tmp = e->sibling;
⚫
free(e);
⚫
}
⚫
}


⚫
//#define BIG_EXAMPLE
int main(void)
int main(void)
{
{
Line 186: Line 204:
int i, j, c;
int i, j, c;


# define N_NODES 2000
# define N_NODES 4000
node_t *nodes = calloc(sizeof(node_t), N_NODES);
node_t *nodes = calloc(sizeof(node_t), N_NODES);


Line 197: Line 215:
for (i = 0; i < N_NODES; i++) {
for (i = 0; i < N_NODES; i++) {
for (j = 0; j < N_NODES; j++) {
for (j = 0; j < N_NODES; j++) {
/* majority of runtime is actually spent here */
if (i == j) continue;
if (i == j) continue;
c = rand() % 100;
c = rand() % 100;
Line 214: Line 233:
}
}


#if 0
/*
/* real programmers don't free memories (they use Fortran) */
for (i = 0; i < N_NODES; i++)
free_edges(nodes + i);
free_edges();
free(heap);
free(heap);
free(nodes);
free(nodes);
#endif
*/
return 0;
return 0;
}</lang>output<pre>
}</lang>output<pre>
Retrieved from "https://rosettacode.org/wiki/Dijkstra%27s_algorithm"