다익스트라(Dijkstra) 알고리즘의 재발견 > 통계용어

본문 바로가기
서울논문컨설팅 / 무료상담 010-2556-8816
신뢰할수 있는 서울대 박사님들이 함께합니다. seoulpaper@daum.net, 02-715-6259


Home > 통계 > 통계용어
통계용어

다익스트라(Dijkstra) 알고리즘의 재발견


 



다익스트라 알고리즘의 pseudo-code와 C 코드는 위키피디아에 잘 나와 있으므로 그곳을 참고한다. 이 글은 어떻게 그 알고리즘을 생각하게 되었을까 를 내 나름대로 생각해 본 후 그에 대하여 쓴 글이다. 

요약
 다익스트라 최단경로 알고리즘은 다음과 같이 생각해 볼 수 있다. 즉, 경로의 그래프를 실로 되어 있다고 생각하고, 각 지점은 매듭으로 되어 있다고 가정하자. 이와 같은 상황에서 주어진 두 지점을 잇는 최단경로를 찾기 위해서는 그 주어진 두 점을 양 끝으로 잡아 당겼을 때 생기는 직선이 된다. 이것은 자명하다1

   다익스트라 알고리즘은, 주어진 경로(그래프)에서 시작점이 주어졌을 때, 각 점으로 가는 최단경로를 구하는 알고리즘이다. 어느 날 나는 그가 어떻게 그 알고리즘을 생각했는지 궁금했다. 그 후 한 가지 아이디어를 생각해 낸 후, 알고리즘으로 바꾸자 다익스트라 알고리즘이 되었다. 

   아이디어는 매우 단순하다. 우선 출발점과 시작점을 생각한 후, 두 지점을 잇는 최단 경로는 두 점을 양끝으로 잡아 당겼을 때 생기는 직선이라는 것이다. 

step1

위와 같은 그래프가 주어져 있고, A와 I 를 잇는 최단 경로를 알고자 한다면, A와 I 를 잡고 양 끝으로 잡아 당기면 되는 것이다.

 

 

step2

 

 



위와 같은 생각을 정리를 해보자면, 도착점이 어디든 그 점과 시작점을 잡고 양끝으로 잡아 당기면 최단경로가 나오는데, 문제는 어떻게 중간에 있는 노드들을 찾을 것인가 하는 것이다. 결국 시작점과 인접한 노드들부터 그 거리를 계산해야 하는데, 그림으로 나타내면 다음과 같다. 

step3

우선 A 의 근접 노드들을 생각해 보자. 아직 이 노드들 중 없애야 할 것을 알 수는 없다. 따라서, 이 인접 노드들의 인접 노드들을 생각해 보자. 

step4

위 그림에서 보면 붉고 굵은 선으로 되어 있는 경로에 연결된 D, F, G, H 가 A 에서 거리(여기서 모든 edge는 거리가 1로 가정)가 2인 노드들이다. 이 노드들 중에 특히 G를 생각해 보자. 왜냐 하면 A에서 G 로 가는, 길이가 2인 경로가 여러 개이기 때문이다. 

step5

이 경우, A에서 G로 가는 경로만 따로 떼어서 생각을 해보면, 

step6


최단 경로는 결국 A와 G를 양끝으로 잡아 당긴 경로이다. 

step7

이 경로를 다시 원래의 그래프로 가져가면, 

step8

이렇게 된다. 이것은, 즉, A에서 G로 가는 3개의 경로

A -> B -> G
A -> E -> G
A -> B -> E -> G

중 A -> E -> G 를 선택해야 함을 의미한다. 지금까지의 생각을 곧바로 재귀시켜버리면 다익스트라 알고리즘이 나온다. 즉, 트리로 바꾸어서 똑같은 논리를 따라 갈 수 있다. 이제, 본격적으로 문제를 풀어 보자. 

우선 각 edge 가 다른 길이를 갖는 그래프를 하나 만들자. 

step9


A 에서 출발할 것이므로, A 를 root note 로 두고 한 단계 덧붙이자. 

step10

역시 이 단계에선 버릴 노드를 알 단서가 없다. 한 단계 더 덧붙이자. 

step11

이 단계에선 여러 노드가 겹치는 것을 볼 수 있다. E 를 생각해 보자. 결국 이것은 A 에서 E 로 가는 여러 경로가 존재함을 의미한다. 이 여러 경로 중 어느 것을 선택할 것인가는 자명하다. 

step12

A에서 E 로 오는 경로가 가장 짧은 것만 남겨 두고 나머지는 버린다. 이 단계가 바로 위에서 그래프를 실로 된 것으로 생각했을 때 시작 노드와 끝 노드를 양끝으로 잡아 당기는 상황을 표현한 것이다. 

step13

이런 식으로 나머지 겹치는 노드들에 대해서도 같은 절차를 적용하면 결과적으로 다음과 같이 된다. 

step14

이젠 더이상 버릴 노드가 없다. 이 상태에서 남아 있는 노드들을 가지고 한 단계 또 늘려 보자. 

step15

역시 같은 논리로, 새로 추가된 노드들에 대하여, 그 노드로 가는 중복경로 중 가장 짧은 것만 남기고 나머지는 지운다. 그러면 다음과 같이 된다. 

step16

이제 더이상 추가할 노드가 없다. 그러므로 끝. 


그냥 단순히 그래프에서 양 끝으로 잡아 당기는 것은 약간 혼동될 수 있는데, 트리로 바꾼 것은 쉽게 이해할 수 있는 형태이다. 트리로 표현한 절차를 알고리즘으로 옮기면 정확히 다익스트라 알고리즘이 된다.  

번호 제목 글쓴이 날짜 조회 수
열람중 다익스트라(Dijkstra) 알고리즘의 재발견 서울논문 03-15 2046
14 상관계수와 결정계수의 관계 서울논문 03-15 12693
13 그리스어/라틴어 알파벳 발음 서울논문 03-22 13031
12 통계유의도 서울논문 08-07 2160
11 Truncated mean 서울논문 12-27 2274
10 부트스트랩법 서울논문 07-06 2802
9 모수위의 모자(hat)-모수의 추정치 서울논문 10-06 4082
8 회귀분석의 다양한 종류들 서울논문 10-06 3659
7 모형적합(model fitting) 또는 모수추정(parameter estimation) 서울논문 10-06 2831
6 최대우도법(maximum likelihood) 서울논문 10-06 6090
5 표본 (sample) 서울논문 08-07 1304
4 추출틀 (frame) 서울논문 08-07 1653
3 추출단위 (sampling unit) 서울논문 08-07 2170
2 모집단 (population) 서울논문 08-07 1418
1 조사단위 (element) 서울논문 08-07 1808

대표:이광조ㅣ사업자등록번호: 643-09-02202ㅣ대표전화: 02-715-6259ㅣ서울시 용산구 효창원로 188