Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|C}}: buthered the program so it runs faster for large graph
m (→{{header|C}}: unused vars) |
(→{{header|C}}: buthered the program so it runs faster for large graph) |
||
Line 58:
#include <stdlib.h>
#include <string.h>
//#define BIG_EXAMPLE▼
typedef struct node_t node_t, *heap_t;
typedef struct edge_t edge_t;
struct edge_t {
node_t *nd; /* target of this edge */
edge_t *sibling;/* for singly linked list */
int len; /* edge cost */
};
struct node_t {
edge_t *edge; /* singly linked list of edges */
node_t *via; /* where previous node is in shortest path */
double dist; /* distance from origining node */
char name[8]; /* the, er, name */
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.
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;
}▼
{▼
for (; edge_root; edge_root = e_next) {
e_next = edge_root[BLOCK_SIZE].sibling;
}▼
}
/* --- priority queue stuff --- */
heap_t *heap;
int heap_len;
Line 84 ⟶ 121:
if (nd->via && d >= nd->dist) return;
/* find existing heap entry, or create
nd->dist = d;
nd->via = via;
/* upheap */
Line 123 ⟶ 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)
{
Line 155 ⟶ 184:
}
▲void free_edges(node_t *nd)
▲{
▲ free(e);
▲ }
▲}
▲//#define BIG_EXAMPLE
int main(void)
{
Line 186 ⟶ 204:
int i, j, c;
# define N_NODES
node_t *nodes = calloc(sizeof(node_t), N_NODES);
Line 197 ⟶ 215:
for (i = 0; i < N_NODES; i++) {
for (j = 0; j < N_NODES; j++) {
/* majority of runtime is actually spent here */
if (i == j) continue;
c = rand() % 100;
Line 214 ⟶ 233:
}
#if 0
/* real programmers don't free memories (they use Fortran) */
free(heap);
free(nodes);
#endif
return 0;
}</lang>output<pre>
| |||