다익스트라의 구현 1

선형탐색으로 구현한 일반적인 다익스트라 구현방법입니다.

직관적이고, 작성이쉬운 장점이 있으나, 최단거리를구하기위해 짧은거리부터 찾아나가는 연산과 전체적인 다익스트라를 수행하는 연산이 약 n^2번 까지도 돌 수 있으므로 평균 시간복잡도가 O(N^2)입니다.

아래 경우를 예시로 하여 0번노드에서부터의 다익스트라를 구현해보았습니다.

코드

#include<cstdio>
#define INF 21474836

#define MAX_VERTEX 4

int weight[MAX_VERTEX][MAX_VERTEX] =
{
	{0,5,1,INF},
	{5,0,2,INF},
	{1,2,0,3},
	{INF,INF,3,0}
};
bool visited[4];
int d[4];
void dijkstra(int start);
int  small_index();
int main()
{
	dijkstra(0);
	for (int i = 0; i < 4; i++)
		printf("%d ", d[i]);
	puts("");
}
void dijkstra(int start)
{
	for (int i = 0; i < 4; i++)
		d[i] = weight[start][i];
	visited[start] = 1;

	//첫째노드와 마지막 노드에서 최단거리를 구할필요는없으므로
	//i<4가 아닌 i<2
	for (int i = 0; i < 2; i++)
	{
		int current = small_index();
		visited[current] = 1;
		for (int j = 0; j < 4; j++)
		{
			if (!visited[j]) {
				//current까지의최단거리+현재~도착까지의거리<도착까지의최단거리라면,
				if ((d[current] + weight[current][j]) < d[j])
				{
					//작은값으로 갱신
					d[j] = d[current] + weight[current][j];
				}
			}
		}
	}
}
int  small_index()
{
	int min = INF;
	int index = 0;
	for (int i = 0; i < 4; i++) {
		if (d[i] < min && !visited[i])
		{
			min = d[i];
			index = i;
		}
	}
	return index;

}

결과