最短経路求解プログラム

/*		bfs.c		横形探索		breadth-first search	*/
#include <stdio.h>
#include <stdlib.h>

#define		START		0		/* 出発点の番号 */
#define		NMAX		100		/* 点の数の上限	*/

static char adjacent[NMAX + 1][NMAX + 1];	/* 隣接行列 */
int n = 9;						/* 点の数 */

typedef	struct queue					/* 待ち行列 */
		{
			int item;
			struct queue *next;
		}								QUEUE;

QUEUE *head, *tail;

/* function prototype declaration */

void initialize_queue(void);		/* 待ち行列の初期化 */
void addqueue(int x);				/* 待ち行列への挿入 */
int removequeue(void);				/* 待ち行列からの取り消し */

void initialize_queue(void)		/* 待ち行列の初期化 */
{
	head = tail = (QUEUE *)malloc(sizeof(QUEUE));
	if(head == NULL)
	{
		fprintf(stderr, "Error : out of memory.\n");
		exit(-1);
	}
}

void addqueue(int x)			/* 待ち行列への挿入 */
{
	tail->item = x;
	tail->next = (QUEUE *)malloc(sizeof(QUEUE));
	if(tail->next == NULL)
	{
		fprintf(stderr, "Error : out of memory.\n");
		exit(-1);
	}
	tail = tail->next;
}

int removequeue(void)			/* 待ち行列からの取り消し */
{
	int x;
	QUEUE *p;

	p = head;
	head = p->next;
	x = p->item;
	free((char *)p);
	return x;
}

int main(void)
{
	int i, j;
	static int distance[NMAX + 1], prev[NMAX + 1];

	initialize_queue();

/* 隣接行列の設定 */
/*                */
/*   0 - 1 - 2    */
/*   |   |   |    */
/*   3 - 4 - 5    */
/*   |   |   |    */
/*   6 - 7 - 8    */
/*                */
	adjacent[0][1] = adjacent[1][0] = 1;
	adjacent[1][2] = adjacent[2][1] = 1;
	adjacent[3][4] = adjacent[4][3] = 1;
	adjacent[4][5] = adjacent[5][4] = 1;
	adjacent[6][7] = adjacent[7][6] = 1;
	adjacent[7][8] = adjacent[8][7] = 1;
	adjacent[0][3] = adjacent[3][0] = 1;
	adjacent[3][6] = adjacent[6][3] = 1;
	adjacent[1][4] = adjacent[4][1] = 1;
	adjacent[4][7] = adjacent[7][4] = 1;
	adjacent[2][5] = adjacent[5][2] = 1;
	adjacent[5][8] = adjacent[8][5] = 1;

	for(i = 1; i <= n; i++)	distance[i] = -1;
	addqueue(START);
	distance[START] = 0;

	do
	{
		i = removequeue();
		for(j = 1; j <= n; j++)
		{
			if(adjacent[i][j] != 0 && distance[j] < 0)
			{
				addqueue(j);
				distance[j] = distance[i] + 1;
				prev[j] = i;
			}
		}
	}while(head != tail);

	printf("点  直前の点  最短距離\n");
	for(i = 1; i <= n; i++)
		if(distance[i] > 0)	printf("%2d%10d%10d\n", i, prev[i], distance[i]);

	return 1;
}

点  直前の点  最短距離
 1         0         1
 2         1         2
 3         0         1
 4         1         2
 5         2         3
 6         3         2
 7         4         3
 8         5         4

/*		dijkstra.c		最短経路問題	shortest path problem */
#include <stdio.h>
#include <stdlib.h>

#define		N			9
#define		START		0
#define		FALSE		0
#define		TRUE		1
#define		INT_MAX		999

void readweight(int **weight)
{
	int i, j;

	for(i = 0; i < N; i++)	for(j = 0; j < N; j++)	weight[i][j] = INT_MAX;
/*                                  */
/*        ->(1)      ->(2)          */
/*    0   <-(2)   1  <-(1)  2       */
/*                                  */
/*(1)↓↑(2) (3)↓↑(1) (2)↓↑(2)  */
/*                                  */
/*        ->(2)      ->(1)          */
/*    3   <-(3)   4  <-(3)  5       */
/*                                  */
/*(2)↓↑(1) (4)↓↑(1) (7)↓↑(1)  */
/*                                  */
/*        ->(2)      ->(1)          */
/*    6   <-(1)   7  <-(2)  8       */
/*                                  */
	weight[0][1] = 1;
	weight[1][0] = 2;
	weight[1][2] = 2;
	weight[2][1] = 1;
	weight[3][4] = 2;
	weight[4][3] = 3;
	weight[4][5] = 1;
	weight[5][4] = 3;
	weight[6][7] = 2;
	weight[7][6] = 1;
	weight[7][8] = 1;
	weight[8][7] = 2;
	weight[0][3] = 1;
	weight[3][0] = 2;
	weight[3][6] = 2;
	weight[6][3] = 1;
	weight[1][4] = 3;
	weight[4][1] = 1;
	weight[4][7] = 4;
	weight[7][4] = 1;
	weight[2][5] = 2;
	weight[5][2] = 2;
	weight[5][8] = 7;
	weight[8][5] = 1;
}

int main(void)
{
	int i, j, next, min;
	int *distance, *prev, *visited;
	int **weight, **p;

	distance = (int *)calloc(N, sizeof(int));
	prev = (int *)calloc(N, sizeof(int));
	visited = (int *)calloc(N, sizeof(int));
	weight = (int **)malloc(N * sizeof(int *));
	*weight = (int *)malloc(N * N * sizeof(int));
	for(p = weight, i = 1; i < N; i++, p++)	*(p + 1) = *p + N;

	readweight(weight);		/* 距離 weight[0..n-1][0..n-1] を読む */
/*
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)	printf("%2d", weight[i][j]);
		printf("\n");
	}
*/
	for(i = 0; i < N; i++)
	{
		visited[i] = FALSE;
		distance[i] = INT_MAX;
	}
	distance[START] = 0;
	next = START;
	do
	{
		i = next;
		visited[i] = TRUE;
		min = INT_MAX;
		for(j = 0; j < N; j++)
		{
			if(visited[j])	continue;
			if(weight[i][j] < INT_MAX
				&& distance[i] + weight[i][j] < distance[j])
			{
				distance[j] = distance[i] + weight[i][j];
				prev[j] = i;
			}
			if(distance[j] < min)
			{
				min = distance[j];
				next = j;
			}
		}
	}while(min < INT_MAX);
	printf("点  直前の点  最短距離\n");
	for(i = 0; i < N; i++)
		if(i != START && visited[i])
			printf("%2d%10d%10d\n", i, prev[i], distance[i]);
	return 1;
}

点  直前の点  最短距離
 1         0         1
 2         1         3
 3         0         1
 4         3         3
 5         4         4
 6         3         3
 7         6         5
 8         7         6