Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|C}}: new
(→{{header|C}}: new) |
|||
Line 51:
'''Extra Credit:''' Document the specific algorithm implemented. The <nowiki>{{trans}}</nowiki> template is sufficient. Otherwise add text outside of your program or add comments within your program. This is not a requirement to explain ''how'' the algorithm works, but to state ''which'' algorithm is implemented. If your code follows an external source such as the Wikipedia pseudocode, you can state that. You can state if it is Dijkstra's original algorithm or some more efficient variant. It is relevant to mention things like priority queues, heaps, and expected time complexity in big-O notation. If a priority queue is used, it is important to discuss how the step of decreasing the distance of a node is accomplished, and whether it is linear or logarithmic time.
=={{header|C}}==
Standard binary heap-as-priority queue affair. Only that each node links back to its heap position for easier update.
There are two <code>main()</code> functions to choose from, one is for task example, the other is a much heavier duty test.
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node_t node_t, *heap_t;
typedef struct edge_t edge_t;
struct edge_t {
node_t *nd;
edge_t *sibling;
int len;
};
struct node_t {
edge_t *edge; /* singly linked list of edges */
node_t *via; /* where previous node is in shortest path */
double dist;
char name[8];
int heap_idx; /* link to heap position for updating distance */
};
heap_t *heap;
int heap_len;
void set_dist(node_t *nd, node_t *via, double d)
{
int i, j;
/* already knew better path */
if (nd->via && d >= nd->dist) return;
/* find existing or create new heap enntry */
nd->dist = d;
nd->via = via;
if (!(i = nd->heap_idx))
i = ++heap_len;
/* upheap */
for (; i > 1 && nd->dist < heap[j = i/2]->dist; i = j)
(heap[i] = heap[j])->heap_idx = i;
heap[i] = nd;
nd->heap_idx = i;
}
node_t * pop_queue()
{
node_t *nd, *tmp;
int i, j;
if (!heap_len) return 0;
/* remove leading element, pull tail element there and downheap */
nd = heap[1];
tmp = heap[heap_len--];
for (i = 1; i < heap_len && (j = i * 2) <= heap_len; i = j) {
if (j < heap_len && heap[j]->dist > heap[j+1]->dist) j++;
if (heap[j]->dist >= tmp->dist) break;
(heap[i] = heap[j])->heap_idx = i;
}
heap[i] = tmp;
tmp->heap_idx = i;
return nd;
}
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)
{
node_t *lead;
edge_t *e;
set_dist(start, start, 0);
while ((lead = pop_queue()))
for (e = lead->edge; e; e = e->sibling)
set_dist(e->nd, lead, lead->dist + e->len);
}
void show_path(node_t *nd)
{
if (nd->via == nd)
printf("%s", nd->name);
else if (!nd->via)
printf("%s(unreached)", nd->name);
else {
show_path(nd->via);
printf("-> %s(%g) ", nd->name, nd->dist);
}
}
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
#ifndef BIG_EXAMPLE
int main(void)
{
int i, j;
# define N_NODES ('f' - 'a' + 1)
node_t *nd, *nodes = calloc(sizeof(node_t), N_NODES);
for (i = 0; i < N_NODES; i++)
sprintf(nodes[i].name, "%c", 'a' + i);
# define E(a, b, c) add_edge(nodes + (a - 'a'), nodes + (b - 'a'), c)
E('a', 'b', 7); E('a', 'c', 9); E('a', 'f', 14);
E('b', 'c', 10);E('b', 'd', 15);E('c', 'd', 11);
E('c', 'f', 2); E('d', 'e', 6); E('e', 'f', 9);
# undef E
heap = calloc(sizeof(heap_t), N_NODES + 1);
heap_len = 0;
calc_all(nodes);
for (i = 0; i < N_NODES; i++) {
show_path(nodes + i);
putchar('\n');
}
return 0;
}
#else /* BIG_EXAMPLE */
int main(void)
{
int i, j, c;
# define N_NODES 2000
node_t *nd, *nodes = calloc(sizeof(node_t), N_NODES);
for (i = 0; i < N_NODES; i++)
sprintf(nodes[i].name, "%d", i + 1);
/* given any pair of nodes, there's about 50% chance they are not
connected; if connected, the cost is randomly chosen between 0
and 49 (inclusive! see output for consequences) */
for (i = 0; i < N_NODES; i++) {
for (j = 0; j < N_NODES; j++) {
if (i == j) continue;
c = rand() % 100;
if (c < 50) continue;
add_edge(nodes + i, nodes + j, c - 50);
}
}
heap = calloc(sizeof(heap_t), N_NODES + 1);
heap_len = 0;
calc_all(nodes);
for (i = 0; i < N_NODES; i++) {
show_path(nodes + i);
putchar('\n');
}
/*
for (i = 0; i < N_NODES; i++)
free_edges(nodes + i);
free(heap);
free(nodes);
*/
return 0;
}
#endif</lang>output<pre>
a
a-> b(7)
a-> c(9)
a-> c(9) -> d(20)
a-> c(9) -> d(20) -> e(26)
a-> c(9) -> f(11)
</pre>
=={{header|C++}}==
(Modified from [http://en.literateprograms.org/Dijkstra%27s_algorithm_%28C_Plus_Plus%29 LiteratePrograms], which is MIT/X11 licensed.)
| |||