2 !!DESCRIPTION!! Dijkstras Algorithm
4 !!LICENCE!! Public Domain
5 !!AUTHOR!! Groepaz/Hitmen
12 #define NULL ((void*)0)
15 #define DIJKSTRA_INFINITY (0xffff)
17 #define DIJKSTRA_FLAG_UNVISITED (0x0)
19 #define DIJKSTRA_FLAG_OPEN (0x1)
21 #define DIJKSTRA_FLAG_CLOSED (0x2)
23 typedef struct _DIJKSTRA_EDGE {
24 struct _DIJKSTRA_NODE *NEXTNODE;
25 unsigned short DISTANCE;
28 typedef struct _DIJKSTRA_NODE {
32 unsigned short MINDIST;
33 struct _DIJKSTRA_NODE *PREVIOUS;
36 /* init with graph, startnode, working-array */
37 void Dijkstra_Init(const DIJKSTRA_NODE *graph,DIJKSTRA_NODE *start,DIJKSTRA_NODE *nodes);
39 /* call main algo with working-array */
40 void Dijkstra_Search(DIJKSTRA_NODE *nodes);
42 /* print path, call with working-array, endnode */
43 void Dijkstra_Path(DIJKSTRA_NODE *nodes,DIJKSTRA_NODE *end);
45 /* print table, call with working-array, current node */
46 void Dijkstra_Table(DIJKSTRA_NODE *nodes,DIJKSTRA_NODE *current);
48 /* internally used routines */
50 unsigned short Dijkstra_Distance(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode);
51 void Dijkstra_Relax(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode);
52 DIJKSTRA_NODE *Dijkstra_NextCheapest(DIJKSTRA_NODE *graph);
53 unsigned short Dijkstra_CountUnvisited(DIJKSTRA_NODE *graph);
55 /* define to get printed info as the algorithm proceeds */
56 #define DIJKSTRA_PRINTDEBUG
58 /* the working array */
59 DIJKSTRA_NODE mynodes[0x10];
61 /* test-network data (mypoints and myedges) */
63 const DIJKSTRA_EDGE myedges_A[]={
67 const DIJKSTRA_EDGE myedges_B[]={
73 const DIJKSTRA_EDGE myedges_C[]={
78 const DIJKSTRA_EDGE myedges_D[]={
83 const DIJKSTRA_EDGE myedges_E[]={
87 const DIJKSTRA_EDGE myedges_F[]={
91 const DIJKSTRA_EDGE myedges_G[]={
96 const DIJKSTRA_EDGE myedges_H[]={
101 const DIJKSTRA_EDGE myedges_I[]={
105 const DIJKSTRA_EDGE myedges_J[]={
109 const DIJKSTRA_EDGE myedges_K[]={
113 const DIJKSTRA_EDGE myedges_L[]={
118 const DIJKSTRA_NODE mypoints[]={
119 {(DIJKSTRA_EDGE *)&myedges_A[0],'A'},
120 {(DIJKSTRA_EDGE *)&myedges_B[0],'B'},
121 {(DIJKSTRA_EDGE *)&myedges_C[0],'C'},
122 {(DIJKSTRA_EDGE *)&myedges_D[0],'D'},
123 {(DIJKSTRA_EDGE *)&myedges_E[0],'E'},
124 {(DIJKSTRA_EDGE *)&myedges_F[0],'F'},
125 {(DIJKSTRA_EDGE *)&myedges_G[0],'G'},
126 {(DIJKSTRA_EDGE *)&myedges_H[0],'H'},
127 {(DIJKSTRA_EDGE *)&myedges_I[0],'I'},
128 {(DIJKSTRA_EDGE *)&myedges_J[0],'J'},
129 {(DIJKSTRA_EDGE *)&myedges_K[0],'K'},
130 {(DIJKSTRA_EDGE *)&myedges_L[0],'L'},
135 * initialize working-array
138 void Dijkstra_Init(const DIJKSTRA_NODE *graph,DIJKSTRA_NODE *start,DIJKSTRA_NODE *nodes) {
139 while(graph->EDGES!=NULL) {
140 nodes->EDGES=graph->EDGES;
141 nodes->TAG=graph->TAG;
142 nodes->FLAG=DIJKSTRA_FLAG_UNVISITED;
143 nodes->MINDIST=DIJKSTRA_INFINITY;
144 nodes->PREVIOUS=NULL;
150 start->FLAG=DIJKSTRA_FLAG_OPEN;
151 start->PREVIOUS=NULL;
157 * compute the distance between two Nodes in the Graph
160 unsigned short Dijkstra_Distance(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode){
163 edge=currnode->EDGES;
166 if(edge->NEXTNODE == nextnode){
167 return(edge->DISTANCE);
174 return(DIJKSTRA_INFINITY);
178 * 'relax' one node against another
181 void Dijkstra_Relax(DIJKSTRA_NODE *currnode,DIJKSTRA_NODE *nextnode){
182 unsigned short newdist;
184 #ifdef DIJKSTRA_PRINTDEBUG
185 printf("relax >%c< to >%c<\n",currnode->TAG,nextnode->TAG);
188 newdist=currnode->MINDIST+Dijkstra_Distance(currnode,nextnode);
190 if((nextnode->MINDIST)>(newdist)){
191 nextnode->MINDIST=newdist;
192 nextnode->PREVIOUS=currnode;
198 * find the yet unprocessed Node with the currently
199 * smallest estimated MINDIST
202 DIJKSTRA_NODE *Dijkstra_NextCheapest(DIJKSTRA_NODE *graph){
203 unsigned short mindist;
207 mindist=DIJKSTRA_INFINITY;
209 while(graph->EDGES!=NULL) {
210 if(graph->FLAG!=DIJKSTRA_FLAG_CLOSED){
211 if(!(mindist<graph->MINDIST)){
212 mindist=graph->MINDIST;
221 #ifdef DIJKSTRA_PRINTDEBUG
222 if(node!=NULL) printf("next cheapest Node: >%c<\n",node->TAG);
229 * count number of Nodes that are left for processing
232 unsigned short Dijkstra_CountUnvisited(DIJKSTRA_NODE *graph){
237 while(graph->EDGES!=NULL) {
238 if(graph->FLAG!=DIJKSTRA_FLAG_CLOSED){
250 * Dijkstra-Algorithmus main processing
253 void Dijkstra_Search(DIJKSTRA_NODE *graph){
254 DIJKSTRA_NODE *currnode,*nextnode;
259 while(Dijkstra_CountUnvisited(graph)>0){
260 edge=currnode->EDGES;
261 while(edge->NEXTNODE!=NULL){
262 nextnode=edge->NEXTNODE;
263 if(nextnode->FLAG!=DIJKSTRA_FLAG_CLOSED){
265 nextnode->FLAG=DIJKSTRA_FLAG_OPEN;
267 Dijkstra_Relax(currnode,nextnode);
268 #ifdef DIJKSTRA_PRINTDEBUG
269 Dijkstra_Table(graph,currnode);
274 currnode=Dijkstra_NextCheapest(graph);
275 currnode->FLAG=DIJKSTRA_FLAG_CLOSED;
280 * print the Path from start Node to one other Node
283 void Dijkstra_Path(DIJKSTRA_NODE *graph,DIJKSTRA_NODE *end){
284 DIJKSTRA_NODE *currnode,*nextnode;
286 printf("Path from >%c< to >%c< : ",end->TAG,graph->TAG);
290 while(currnode->PREVIOUS!=NULL){
291 printf(">%c< ",currnode->TAG);
292 currnode=currnode->PREVIOUS;
295 printf(">%c<\n",currnode->TAG);
299 * print working-array as a table
302 void Dijkstra_Table(DIJKSTRA_NODE *graph,DIJKSTRA_NODE *current){
305 printf("----------------------\n");
308 g=graph;while(g->EDGES!=NULL) {
309 printf("-->%c<-|",g->TAG);
315 g=graph;while(g->EDGES!=NULL) {
316 printf(" %5u|",g->MINDIST);
322 g=graph;while(g->EDGES!=NULL) {
325 case DIJKSTRA_FLAG_OPEN:
329 case DIJKSTRA_FLAG_CLOSED:
333 if(g->MINDIST!=DIJKSTRA_INFINITY){
345 g=graph;while(g->EDGES!=NULL) {
346 if(g->PREVIOUS==NULL)
349 printf(" (%c) |",g->PREVIOUS->TAG);
354 printf("----------------------\n");
359 /* init with graph, startnode, working-array */
360 Dijkstra_Init(&mypoints[0],&mynodes[0],&mynodes[0]);
361 /* call main algo with working-array */
362 Dijkstra_Search(&mynodes[0]);
363 /* print table, call with working-array, endnode */
364 Dijkstra_Table(&mynodes[0],&mynodes[11]);
365 /* print path, call with working-array, endnode */
366 Dijkstra_Path(&mynodes[0],&mynodes[11]);