[알고리즘] Dijikstra 최단경로 알고리즘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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