dijkstra.c

#ifdef SHELL
gcc -Wall -Werror $0 && ./a.out
exit $?
#endif

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define DIJ_MAX_PATHS 10
#define INFINITY 10000

typedef struct st_node node_t;
typedef struct st_path path_t;

typedef struct st_path {
	node_t * node;
	int distance;
	bool best;
} path_t;

typedef struct st_node {
	int distance;
	char name[10];
	path_t paths[DIJ_MAX_PATHS];
	bool visited;
} node_t;

void add_path_once( node_t * a, node_t * b, int distance ) {
	path_t * path = a->paths;
	while( path->node )
		path++;
	path->node = b;
	path->distance = distance;
}

void add_path( node_t * a, node_t * b, int distance ) {
	add_path_once( a, b, distance );
	add_path_once( b, a, distance );
}

void node_mark_best_path( node_t * node, path_t * m ) {
	path_t * p = node->paths;
	for( p = node->paths ; p->node ; p++ )
		p->best = (p == m);
}

void nodes_list( node_t ** nodes ) {
	node_t * n;
	while( (n = *nodes) ) {
		printf("* %s [%d] %s\n", n->name, n->distance, n->visited ? "visited" : "-" );
		path_t *p;
		for( p = n->paths; p->node; p++ )
			printf("  --(%d)--> %s %s\n", p->distance, p->node->name, p->best ? "[BEST]" : "" );
		nodes++;
	}
}

int dijkstra_node_distance( node_t * node ) {
	path_t * p;

	if ( ! node->visited ) {
		printf("dijkstra_node_distance( %s )...\n", node->name );
		node->visited = true;
		for( p = node->paths; p->node; p++) {
			int d = dijkstra_node_distance( p->node ) + p->distance ;
			if ( d < node->distance ) {
				node->distance = d;
				node_mark_best_path( node, p );
			}
		}
		printf("dijkstra_node_distance( %s ): %d\n", node->name, node->distance );
	}
	
	return node->distance;
}

void dijskstra_nodes( node_t ** nodes ) {
	node_t * n;
	while( (n = *nodes) ) {
		dijkstra_node_distance( n );
		nodes++;
	}
}

void dijkstra_solution( node_t * node ) {
	printf("%s[%d]", node->name, node->distance );

	path_t * p;
	for( p = node->paths; p->node; p++ ) {
		if ( p->best ) {
			printf(" --(%d)--> ", p->distance );
			dijkstra_solution( p->node );
			break;
		}
	}	
}

int main() {

	// Model is: http://www.eoinbailey.com/content/dijkstras-algorithm-illustrated-explanation
	int cnt;	
	for( cnt = 0; cnt < 3; cnt++ ) {
		node_t
			a = {distance:  0, name: "a"},
			b = {distance: INFINITY, name: "b"},
			c = {distance: INFINITY, name: "c"},
			d = {distance: INFINITY, name: "d"},
			e = {distance: INFINITY, name: "e"},
			f = {distance: INFINITY, name: "f"},
			g = {distance: INFINITY, name: "g"},
			h = {distance: INFINITY, name: "h"},
			i = {distance: INFINITY, name: "i"};
	
		add_path( & a, & b, 7 );
		add_path( & a, & c, 4 );
		add_path( & a, & d, 5 );
		add_path( & b, & c, 2 );
		add_path( & b, & e, 25 );
		add_path( & e, & g, 10 );
		add_path( & g, & i, 2 );
		add_path( & c, & h, 9 );
		add_path( & h, & i, 3 );
		add_path( & d, & f, 9 );
		add_path( & f, & h, 20 );

		node_t * nodes [] = { & a, & b, & c, &d, & e, & f, & g, & h, & i, NULL };

		node_t * target;
	
		switch(cnt) {
			case 0:
				target = &i;
				break;
			case 1:
				target = &e;
				break;

			case 2:
				target = &g;
				break;
		}

		dijkstra_node_distance( target );

		nodes_list( nodes );

		printf("Solution for %s: ", target->name);
		dijkstra_solution( target );
		printf("\n");
	}

	return 0;
}

/*
Output:

dijkstra_node_distance( i )...
dijkstra_node_distance( g )...
dijkstra_node_distance( e )...
dijkstra_node_distance( b )...
dijkstra_node_distance( a )...
dijkstra_node_distance( c )...
dijkstra_node_distance( h )...
dijkstra_node_distance( f )...
dijkstra_node_distance( d )...
dijkstra_node_distance( d ): 5
dijkstra_node_distance( f ): 14
dijkstra_node_distance( h ): 13
dijkstra_node_distance( c ): 4
dijkstra_node_distance( a ): 0
dijkstra_node_distance( b ): 6
dijkstra_node_distance( e ): 31
dijkstra_node_distance( g ): 41
dijkstra_node_distance( i ): 16
* a [0] visited
  --(7)--> b 
  --(4)--> c 
  --(5)--> d 
* b [6] visited
  --(7)--> a 
  --(2)--> c [BEST]
  --(25)--> e 
* c [4] visited
  --(4)--> a [BEST]
  --(2)--> b 
  --(9)--> h 
* d [5] visited
  --(5)--> a [BEST]
  --(9)--> f 
* e [31] visited
  --(25)--> b [BEST]
  --(10)--> g 
* f [14] visited
  --(9)--> d [BEST]
  --(20)--> h 
* g [41] visited
  --(10)--> e [BEST]
  --(2)--> i 
* h [13] visited
  --(9)--> c [BEST]
  --(3)--> i 
  --(20)--> f 
* i [16] visited
  --(2)--> g 
  --(3)--> h [BEST]
Solution for i: i[16] --(3)--> h[13] --(9)--> c[4] --(4)--> a[0]
dijkstra_node_distance( e )...
dijkstra_node_distance( b )...
dijkstra_node_distance( a )...
dijkstra_node_distance( c )...
dijkstra_node_distance( h )...
dijkstra_node_distance( i )...
dijkstra_node_distance( g )...
dijkstra_node_distance( g ): 10000
dijkstra_node_distance( i ): 16
dijkstra_node_distance( f )...
dijkstra_node_distance( d )...
dijkstra_node_distance( d ): 5
dijkstra_node_distance( f ): 14
dijkstra_node_distance( h ): 13
dijkstra_node_distance( c ): 4
dijkstra_node_distance( a ): 0
dijkstra_node_distance( b ): 6
dijkstra_node_distance( e ): 31
* a [0] visited
  --(7)--> b 
  --(4)--> c 
  --(5)--> d 
* b [6] visited
  --(7)--> a 
  --(2)--> c [BEST]
  --(25)--> e 
* c [4] visited
  --(4)--> a [BEST]
  --(2)--> b 
  --(9)--> h 
* d [5] visited
  --(5)--> a [BEST]
  --(9)--> f 
* e [31] visited
  --(25)--> b [BEST]
  --(10)--> g 
* f [14] visited
  --(9)--> d [BEST]
  --(20)--> h 
* g [10000] visited
  --(10)--> e 
  --(2)--> i 
* h [13] visited
  --(9)--> c [BEST]
  --(3)--> i 
  --(20)--> f 
* i [16] visited
  --(2)--> g 
  --(3)--> h [BEST]
Solution for e: e[31] --(25)--> b[6] --(2)--> c[4] --(4)--> a[0]
dijkstra_node_distance( g )...
dijkstra_node_distance( e )...
dijkstra_node_distance( b )...
dijkstra_node_distance( a )...
dijkstra_node_distance( c )...
dijkstra_node_distance( h )...
dijkstra_node_distance( i )...
dijkstra_node_distance( i ): 16
dijkstra_node_distance( f )...
dijkstra_node_distance( d )...
dijkstra_node_distance( d ): 5
dijkstra_node_distance( f ): 14
dijkstra_node_distance( h ): 13
dijkstra_node_distance( c ): 4
dijkstra_node_distance( a ): 0
dijkstra_node_distance( b ): 6
dijkstra_node_distance( e ): 31
dijkstra_node_distance( g ): 18
* a [0] visited
  --(7)--> b 
  --(4)--> c 
  --(5)--> d 
* b [6] visited
  --(7)--> a 
  --(2)--> c [BEST]
  --(25)--> e 
* c [4] visited
  --(4)--> a [BEST]
  --(2)--> b 
  --(9)--> h 
* d [5] visited
  --(5)--> a [BEST]
  --(9)--> f 
* e [31] visited
  --(25)--> b [BEST]
  --(10)--> g 
* f [14] visited
  --(9)--> d [BEST]
  --(20)--> h 
* g [18] visited
  --(10)--> e 
  --(2)--> i [BEST]
* h [13] visited
  --(9)--> c [BEST]
  --(3)--> i 
  --(20)--> f 
* i [16] visited
  --(2)--> g 
  --(3)--> h [BEST]
Solution for g: g[18] --(2)--> i[16] --(3)--> h[13] --(9)--> c[4] --(4)--> a[0]

*/