最短経路

[pazumon_2525]

ダイクストラ法の勉強をしています。
プログラムを作成しました。
さらにこれの始めと終わりの最短経路を求めるにはどうしたらよいですか？
よろしくお願いします。

コード:

#include<stdio.h>

#define INF 99999999
#define TRUE 1
#define FALSE 0

int n;
int dist[100][100];
int cost[100];
char fixed[100];

void dijkstra_method()
{
	int i,j,min_node,min;
	
	do
	{
		min = INF;
		min_node = INF;
		
		for(j=0;j<n;j++)
		{
			if(fixed[j])
			{
				for(i=0;i<n;i++)
				{
					if(!fixed[i] && (dist[j][i]>0))
					{
						if(cost[i] >= (dist[j][i] + cost[j]))
						{
							cost[i] = dist[j][i] + cost[j];
							
							if(cost[i] <= min)
							{
								min = cost[i];
								min_node = i;
							}
						}
					}
				}
			}
		}
		if(min_node != INF)
		{
			fixed[min_node] = TRUE;
		}
	}
	while(min_node != INF);
}
int main()
{
	int i,j,start,end;
	
	start = 0;
	end = 2;
	
	n = 5;
	
	for(i=0;i<n;i++)
	{
		cost[i] = INF;
		fixed[i] = FALSE;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			dist[i][j] = 0;
		}
	}
	dist[1][0] = dist[0][1] = 1;
	dist[3][0] = dist[0][3] = 2;
	dist[4][0] = dist[0][4] = 4;
	dist[1][4] = dist[4][1] = 2;
	dist[1][2] = dist[3][1] = 4;
	dist[2][4] = dist[4][2] = 1;
	dist[3][4] = dist[4][3] = 3;
	
	cost[start] = 0;
	fixed[start] = TRUE;
	
	dijkstra_method();
	
	for(i=0;i<n;i++)
	{
		printf("cost[%d]=%d\n",i,cost[i]);
	}
	printf("\n");
	 
	return 0;
}

[みけCAT]

まず、各ノードに「どこから来たか」の情報をもたせます。
そうすると、それをたどることで最短経路が逆順で求まるので、ひっくり返します。

コード:

#include<stdio.h>

#define INF 99999999
#define MAX 100
#define TRUE 1
#define FALSE 0

int n;
int dist[MAX][MAX];
int cost[MAX];
int from[MAX];
char fixed[MAX];

void dijkstra_method(void)
{
	int i,j,min_node,min;
	
	do
	{
		min = INF;
		min_node = INF;
		
		for(j=0;j<n;j++)
		{
			if(fixed[j])
			{
				for(i=0;i<n;i++)
				{
					if(!fixed[i] && (dist[j][i]>0))
					{
						if(cost[i] >= (dist[j][i] + cost[j]))
						{
							cost[i] = dist[j][i] + cost[j];
							from[i] = j;
							
							if(cost[i] <= min)
							{
								min = cost[i];
								min_node = i;
							}
						}
					}
				}
			}
		}
		if(min_node != INF)
		{
			fixed[min_node] = TRUE;
		}
	}
	while(min_node != INF);
}
void print_route(int node)
{
	if(node != INF && node != from[node])
	{
		print_route(from[node]);
		printf("->");
	}
	printf("%d",node);
}
int main(void)
{
	int i,j,start,end;
	
	start = 0;
	end = 2;
	
	n = 5;
	
	for(i=0;i<n;i++)
	{
		cost[i] = INF;
		from[i] = INF;
		fixed[i] = FALSE;
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			dist[i][j] = 0;
		}
	}
	dist[1][0] = dist[0][1] = 1;
	dist[3][0] = dist[0][3] = 2;
	dist[4][0] = dist[0][4] = 4;
	dist[1][4] = dist[4][1] = 2;
	dist[1][2] = dist[3][1] = 4;
	dist[2][4] = dist[4][2] = 1;
	dist[3][4] = dist[4][3] = 3;
	
	cost[start] = 0;
	from[start] = start;
	fixed[start] = TRUE;
	
	dijkstra_method();
	
	for(i=0;i<n;i++)
	{
		printf("cost[%d]=%d\n",i,cost[i]);
	}
	printf("\n");
	print_route(end);
	printf("\n");
	
	return 0;
}

[pazumon_2525]

ソートするということですね。
ありがとうございました。