Dijkstra.c

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

# define NODE_NUM 6
# define MAX_CONNECTION_NUM 10

struct node_t;

struct node_connect_t
{
	struct node_t* node;
	int cost;
};

struct node_t
{
	struct node_connect_t nexts[MAX_CONNECTION_NUM];
	struct node_t* from;
	int cost;
	int id;
};

typedef struct node_connect_t NodeConnect;
typedef struct node_t Node;

NodeConnect CreateNodeConnect(Node* node, int cost)
{
	NodeConnect nc = {node, cost};
	return nc;
}

int nodelen(Node* node)
{
	int i;

	for(i = 0; i < MAX_CONNECTION_NUM; i++)
	{
		if(node->nexts[i].node == NULL)
			break;
	}

	return i;
}

void search(Node* node)
{
	int i;
	int length = nodelen(node);

	for(i = 0; i < length; i++)
	{
		int currentCost = node->cost + node->nexts[i].cost;

		if(node->nexts[i].node->cost > currentCost)
		{
			node->nexts[i].node->cost = currentCost;
			node->nexts[i].node->from = node;
			printf("search: %d -> %d\n", node->id, node->nexts[i].node->id);
			search(node->nexts[i].node);
		}
	}
}

int main()
{
	Node nodes[NODE_NUM];

	int i, j;

	// Init nodes.
	for(i = 0; i < NODE_NUM; i++)
	{
		nodes[i].from = NULL;
		nodes[i].cost = INT_MAX;
		nodes[i].id = i;

		for(j = 0; j < MAX_CONNECTION_NUM; j++)
		{
			nodes[i].nexts[j] = CreateNodeConnect(NULL, 0);
		}
	}

	// Set paths.
	nodes[0].nexts[0] = CreateNodeConnect(&nodes[1], 10);
	nodes[0].nexts[1] = CreateNodeConnect(&nodes[2], 10);
	nodes[1].nexts[0] = CreateNodeConnect(&nodes[0], 10);
	nodes[1].nexts[1] = CreateNodeConnect(&nodes[2], 10);
	nodes[1].nexts[2] = CreateNodeConnect(&nodes[3], 8);
	nodes[2].nexts[0] = CreateNodeConnect(&nodes[0], 10);
	nodes[2].nexts[1] = CreateNodeConnect(&nodes[1], 10);
	nodes[2].nexts[2] = CreateNodeConnect(&nodes[4], 10);
	nodes[3].nexts[0] = CreateNodeConnect(&nodes[1], 8);
	nodes[3].nexts[1] = CreateNodeConnect(&nodes[5], 8);
	nodes[4].nexts[0] = CreateNodeConnect(&nodes[2], 10);
	nodes[4].nexts[1] = CreateNodeConnect(&nodes[5], 10);
	nodes[5].nexts[0] = CreateNodeConnect(&nodes[3], 8);
	nodes[5].nexts[1] = CreateNodeConnect(&nodes[4], 10);

	nodes[0].cost = 0;
	nodes[0].from = &nodes[0];
	search(&nodes[0]);

	Node* node = &nodes[5];

	for(;;)
	{
		if(node == &nodes[0])
			break;

		printf("path: %d <- %d / %d\n", node->from->id, node->id);
		node = node->from;
	}

	return 0;
}