Rosetta Code

Dijkstra's algorithm: Difference between revisions

Page Discussion

Dijkstra's algorithm (view source)

Revision as of 07:17, 29 April 2012

156 bytes removed ,  12 years ago
m
→‎{{header|C}}: unused vars
m (→‎{{header|C}}: unused vars)
Line 54:
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 (look for <code>#define BIG_EXAMPLE</code>), one is for task example, the other is a much heavier duty test case.
<lang c>#include <stdio.h>
#include <stdlib.h>
Line 164:
}
 
 
// #define BIG_EXAMPLE▼
//#ifndefdefine BIG_EXAMPLE
int main(void)
{
▲// #defineifndef BIG_EXAMPLE
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++)
Line 181 ⟶ 182:
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
Line 218 ⟶ 204:
}
 
#endif
 
heap = calloc(sizeof(heap_t), N_NODES + 1);
heap_len = 0;
Line 235 ⟶ 221:
*/
return 0;
#endif}</lang>output<pre>▼
}
 
▲#endif</lang>output<pre>
a
a-> b(7)
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/209825"