최단경로 알고리즘(shortest path algorithm, dijkstra) think Berry

  오늘은 흔히 알고리즘의 대가라고 불리는 크누님(=크누스)과 자주 언급되는 다익스트라의 최단경로 알고리즘을 다루어보겠습니다. 최근에는 자바스크립트를 손 놓고 옛 추억을 되짚고 있어 말이지요. 소스의 출저는 C로쓴 자료구조론이구요. 제 글보다는 관련 단원을 참고하시는게 수학적으로 더 확실합니다만 제 글로써 알고리즘을 이해하신다면 빌어먹을 수학기호와 해석할 수 없는 한글을 읽지 않고 절약된 시간으로 여러분의 인생을 좀 더 의미 있는 곳에 사용하실 수 있을겁니다. 보통 머리가 아파오는 알고리즘은 소스만 나열해놓아서는 그 의도를 파악하기가 쉽지 않습니다. 그래서 주절주절 정의와 수학적 표현을 기술하는데, 어찌된 일인지 이해를 돕기 위한 글이 의미를 알 수 없는 소스코드보다 더 읽기가 어렵습니다. 그럼 시작합니다.


  다익스트라의 최단경로 알고리즘은 갈망법(greedy method)으로 접근합니다. 갈망법은 눈 앞에 보이는데로 계속 최선의 선택을 하는 것입니다. 거시적 관점보다는 인간과 같이 눈 앞에 노인 상황에 탐욕적으로 접근한다고 하여 붙여진 이름이지요. 만약 최소비용신장트리의 프림 알고리즘을 알고 계신다면 이와 유사하다는 것을 느끼실 겁니다.

 

  다익스트라의 최단경로 알고리즘에서는 전제조건이 붙습니다. 정점(vertex)과 정점사이의 간선(edge)을 거치는 비용을 가중치(weight)라고 하는데 이 가중치는 음의 값이어서는 안된다는 것이죠. 만약 음의 값이 있었다간 그 구간을 무한히 돌며 블랙홀 속으로 빨려 들어가버릴 겁니다.



1.jpg

음의 값이 오면 최단 경로가 무의미해집니다. 정점0과 1을 왓다갓다 하면 대체 끝이 어디죠?




  최단경로 알고리즘의 기본 아이디어는 다음과 같습니다.


 

0) 시작점을 '최단경로를 찾은 정점 리스트'에 담아둔다.

1) '최단경로를 찾은 정점 리스트'에 들어있는 정점으로부터 인접한 정점들중 가장 가중치가 적은 정점을 하나를 탐색한다. 이는 곧 해당 정점까지의 최단경로이다.

2)  리스트내에서의 정점들을 기준으로 가장 가중치가 적은 정점을 다시 탐색한다. 이때 발견되는 정점까지의 가중치는 직전 정점까지의 가중치 + 발견된 정정까지의 가중치로 계산된다. (엄밀히 말해 1.과 2.는 같다)

3) 가능한 모든 정점을 연결할 때까지 반복한다.


제가 제 글을 봐도 화가 나는군요. 한줄 요약으로 설명하겠습니다.

시작 정점부터 가장 가까운 정점을 선택하고 이를 리스트에 담아 기억하고 있다가 이들 정점들로부터 시작점으로부터의 가중치가 적은 간선 하나만 선택합니다. 계속 반복해서 모든 경로를 잇게 되면 시작점부터 모든 점까지의 최단경로는 모두 구해지는 것입니다. 그림으로 이해를 돕겠습니다.


 2_1.jpg






  그림을 보시는 바와 같이 최단경로 알고리즘은 시작점으로 부터 모든 정점까지의 최단거리를 계산할 수 있습니다. 시작점으로 부터 가장 가까운 거리의 정점을 우선 찾고 시작점부터 발견된 정점까지의 거리(가중치)를 별도로 기억합니다(distance). 그리고 발견된 모든 정점들로부터 가장 가중치가 적은 정점을 계속해서 찾아나감으로서 최적의 경로를 모두 탐색하는 것입니다. 핵심은 가중치가 누적되고, 가장 적은 가중치의 정점을 계속해서 찾아가는 이른바 갈망법인 것이죠.



 

다음은 C로 쓴 예제소스입니다. C로쓴 자료구조론의 최단경로절을 바탕으로 바로 돌려볼 수 있도록 약간 재구성되었습니다. 방향성 그래프는 2차원 배열로 표현되었습니다.


graph.dat 파일

7
0 1 5
0 3 10
1 2 5
1 4 20
2 4 10
3 4 20
3 5 30
6 3 20

소스코드 파일

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


#define BIG_INT		8192
#define MAX_SIZE	10
#define FOUND 		1
#define NOT_FOUND	-1


void load_graph_from_file(char* filename, int graph[][MAX_SIZE], int* n); 
int choose(int* distance, int* found, int n);
void shortest_path(int v, int graph[][MAX_SIZE], int* distance, int* found,int* pre_vertex,  int n);
void print_path(int* pre_vertex, int n);


int main(int argc, char** argv) {
	int graph[MAX_SIZE][MAX_SIZE];
	int distance[MAX_SIZE];
	int found[MAX_SIZE];
	int pre_vertex[MAX_SIZE];


	int v;
	int n;	// num of vertex


	load_graph_from_file("graph.dat", graph, &n);
	shortest_path(0, graph, distance, found, pre_vertex, n);
	print_path(pre_vertex, n);
	return 0;
}


void load_graph_from_file(char* filename, int graph[][MAX_SIZE], int* n) {
	FILE* fp = fopen(filename, "r");
	int v, w;	// start vertex, end vertex
	int weight;


	int i, j;


	if (fp == NULL) {
		printf("file not found exception.");
		exit(1);
	}
	
	fscanf (fp, "%d", n);
	if (*n > MAX_SIZE) { printf("too many vertex"); exit(1);}
	
	for (i=0; i<*n; ++i) {
		for (j=0; j<*n; ++j) { 
			graph[i][j] = BIG_INT;
		}
	}


	while (!feof(fp)) {
		fscanf(fp,"%d %d %d",&v, &w,&weight);
		graph[v][w] = weight;
	}
}


int choose(int* distance, int* found, int n) { 
	int i;
	int min = INT_MAX;
	int minpos = -1;


	for (i=0; i<n; ++i) { 
		if (found[i] > NOT_FOUND) continue;
		if (distance[i] >=  min) continue;
		
		min = distance[i];
		minpos = i;
	}
	return minpos;
}


void shortest_path(int v, int graph[][MAX_SIZE], int* distance, int* found, int* pre_vertex, int n) {
	int i, u, w;
	//int pre_vertex;


	// init
	for (i=0; i<n; ++i) {
		distance[i] = graph[v][i];
		found[i] = NOT_FOUND;
		if ( distance[i] > 0 && distance[i] < BIG_INT) pre_vertex[i] = v;
		else pre_vertex[i] = -1;
	}


	distance[v] = 0;
	found[v] = FOUND;
	
	for (i=0; i<n-1; ++i) {
		u = choose(distance, found, n);	//가장 가까운 정점을 찾는다.
		found[u] = FOUND;


		for (w=0; w<n; ++w) {		// 최단 경로상의 정점들로부터 인접정점들까지의 모든 distance를 계산한다.
			if (found[w] > NOT_FOUND) continue;
			if (distance[u] + graph[u][w] >= distance[w]) continue;


			distance[w] = distance[u] + graph[u][w];
			pre_vertex[w] = u;
		}
	}
}


void print_path(int* pre_vertex, int n) { 
	int i;
	int cv;	// current vertex
	for (i=0; i<n; ++i) { 
		cv = i;


		printf("shortest path to %d :[%d]", cv, cv);
		while (pre_vertex[cv] >= 0) {
			printf("<-[%d]", pre_vertex[cv]);
			cv = pre_vertex[cv];
		}
		printf("\n");
	}


}

의문사항은 댓글로 남겨주시면 빠르게 답변해드리겠습니다.

~~ 메리 크리스마스



THinkBerry의 생각열매를 함께 나눠요. ThinkBerry.co.kr
TAG

Leave Comments


profileThinkberry에 오신것을 환영해요~ 

Recent Trackback

오늘:
186
어제:
279
전체:
76,325