[알고리즘] Dijkstra's algorithm

안녕하세요. 꿈꾸는 개발자 몽키준입니다.

이번에는 최단 경로(shortest path) 찾기 알고리즘 중의 하나인 데이크스트라 알고리즘(Dijkstra's algorithm) 에 대해 알아보려고 합니다.

네덜란드 컴퓨터 과학자 이름이라는데 발음하기가 어렵네요. 저만 그런가요?

일단 위키에서는 다음과 같이 알고리즘에 대해 소개를 하고 있습니다. 해당 알고리즘의 가정은 일단 출발점/도착점이 정해져야 하며 각 경로는 마이너스(-) 값이 없다는 전제로 수행하게 됩니다. 만약 마이너스 값이 존재한다면 테이블의 없는 경로로 우회하는 경우 기존 값들에 영향을 주기 때문입니다.

어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.

알고리즘에 대한 자세한 설명을 위키 페이지나 다른 블로그를 참조해주시고 여기서는 아래 코드에 대한 설명을 중점으로 다루겠습니다.

우선, 각 구간의 연결선은 테이블로 표시하면 다음과 같습니다.

                         

1. 인덱스 0번째를  출발지로 선택함으로써 2번째, 3번째, 5번째 그리고 6번째가 차례로 업데이트 됩니다. 이때 부모노드 테이블도 함께 업데이트하게 됩니다.

                                 

2. 사용하지 않은 노드 중 가장 짧은 거리인 2번째  노드 선택를 선택하고 인접한 노드의 거리를 업데이트 합니다. 이때 거리는 2번째 노드까지의 거리 와 인접 거리의 합으로 결정이 됩니다.  예로 4번째 노드의 거리는 0->2 거리와 2->4 거리의 합인 31 + 46, 즉 77 이 되고 2번째노드와 인접한 1번째 노드의 경우 0->2, 2->1 를 통해 가는 거리(31 + 21) 보다 기존 0->1 로 가는 거리가 더 짧아 여기서는 굳이 업데이트할 필요가 없겠네요.

                                   

3. 이렇게 계속해서 i 가 노드 개수 N번까지 수행하면 다음과 같이 됩니다.

                                  

                                 

                                

                              

                                

4. 결국 모든 노드를 방문하게 되는 N-1 에서 경로 계산은 완료됩니다. 계산된 결과를 보면 0번째인 출발지에서 6번째인 도착지에 도달하기 위한 거리는 51 이며, 도착지가 다른 노드인 경우, 예를 들면 3번째 노드가 도착지라면 최단거리는 78 이 됩니다.

참고) 이렇게 계속 진행하다 보면 기존에 계산되었던 경로의 거리보다 짧은 거리가 발견되기도 하는데, 이때 기존의 거리정보와 부모 정보를 함께 업데이트 해줘야 합니다. 하지만 이번 예제 에서는 이와 같은 업데이트 동작은 수행하지 않네요.

[소스코드]

/*
   dijkstra's shortest  algorithm
   sample data is 
   1
   7 10
   0 1 32
   0 2 31
   0 5 60
   0 6 51
   1 2 21
   2 4 46
   2 6 25
   3 4 34
   3 5 18
   4 5 40
   4 6 51
 */

#define SIZE 101
#define MAX_VAL (999999)
int result;
int g[SIZE][SIZE];
int dist[SIZE];
int visited[SIZE];
int parent[SIZE];
int N;
int E;

#define TEST_ENABLED
#ifdef TEST_ENABLED
#define _PRT(format, ...) printf(format, __VA_ARGS__)
#define _printData() print_data()
void print_data()
{
	printf("\n====== origin edge ==================\n");
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%6d ", g[i][j]);
		}
		puts("");
	}
	printf("\n======= distance ==================\n");
	for (int i = 0; i < N; i++) {
		printf("%6d ", dist[i]);
	}
	printf("\n======= parent ===========\n");
	for (int i = 0; i < N; i++) {
		printf("%6d ", parent[i]);
	}
	printf("\n======= visited ============\n");
	for (int i = 0; i < N; i++) {
		printf("%6d ", visited[i]);
	}
	printf("\n============================\n");

}

#else
#define _PRT(format, ...)
#endif

void init()
{
	for (int i = 0 ; i < N; i++) {
		for (int j = 0; j < N; j++) {
			g[i][j] = MAX_VAL;
			dist[i] = MAX_VAL;
		}
		visited[i] = 0;
	}
}

// origin should be fixed
void dij(int origin, int dest)
{
	dist[origin] = 0;
	int u; // index which is not visited and has the smallest value in list of dist
	int min; // to find out minimum value

	for (int i = 0; i < N; i++) {
		min = MAX_VAL;
		for (int j = 0; j < N; j++) {
			if (!visited[j] && min > dist[j]) {
				min = dist[j];
				u = j;
			}
		}
		visited[u] = 1;
		if (u == dest) {
			// stop calculating
		//	break;
		}
		for (int j = 0; j < N; j++) {
			if (!visited[j] && dist[j] > dist[u] + g[u][j]) {
				dist[j] = dist[u] + g[u][j];
				// update parent
				parent[j] = u;
			}	
		}
	}
}

int main()
{
	freopen("./sample.txt", "r", stdin);
	int testCase;
	int _start, _end, _value;

	scanf("%d", &testCase);
	for (int index = 1; index <= testCase; index++) {

		scanf("%d", &N);
		scanf("%d", &E);

		init();
		for (int i = 0; i < E; i++){
			scanf("%d", &_start);
			scanf("%d", &_end);
			scanf("%d", &_value);
			g[_start][_end] = _value;
			g[_end][_start] = _value;
		}

		dij(0, N -1);
		_printData();

		printf("#%d %d\n", index, dist[N-1]);
	}

	return 0;
}

팁1 : 만약 출발지/도착지 조합을 매번 다른 값을 전달해 준다면 각각에 대한 최단 경로를 계산할 수 있습니다.

팁2 : 노드수가 많아질수록 처리 속도 저하가 발생하니 특정 부분경로에 대해서는 추가 계산없이 skip 할 수 있도록 가지치기가 필요합니다.