다익스트라 알고리즘은 워낙 유명하고, 많은 (설명)자료들이 있는 알고리즘이지만, 한번에 이해하기가 쉬운 알고리즘은 아니다.


다익스트라 알고리즘은 방향성 있는 그래프에서 임의의 두 노드 간의 최단 거리(간선의 가중치 합)이 가장 적은 경로를 찾는 알고리즘이다. 알고리즘의 기본 구조는 간단하다. 만약 내가 시작 노드 s부터 현재 노드 u까지의 최간 거리 d(u)을 알고 있고, u에서 다음 노드 v까지의 거리 w(u,v)가 주어진다면, s부터 v까지의 거리는 d(u) + w(u,v)가 될 것이다. 그런데, s에서 v까지 갈 때 꼭 u를 거치라는 법은 없다. 다른 경로를 통해서도 s에서 v에 도달할 수 있다. 이  렇게 다른 노드를 거쳐서 v까지 가는 거리 d(v)가 d(u)+w(u,v) 보다 길다면 d(v) 값을 새로 계산한 d(u)+w(u,v)로 갱신한다. 반대로 d(v)가 더 짧다면 이번에 계산한 d(u)+w(u,v)값은 폐기하면 된다.


아래는 위키피디아에 있는 다익스트라 알고리즘 의사코드를 약간 수정한 것이다. 여기서 u는 현재 노드를, v는 u와 연결된 다른 노드를 가리킨다. previous는 v노드로 갈 때 최단 거리가 되는 이전 노드 u를 저장한다. previous에 저장된 노드들을 역추적하면 최단 경로(shortest path)를 알아낼 수 있다.


function dijkstra(G, w, s)

# initialize d and previous

# d: distance from s

# previous: previous node whose distance is minimum

for each vertex v in V(G)

d[v] := infinity

previous[v] := undefined

# 시작 노드에서 시작 노드까지의 거리는 당연히 0

d[s] := 0

S := empty set

Q := set of all vertices


while Q is not empty

u := extract_min(Q)

S += u

for each edge(u, v):

# (다른 경로를 통해 이미 계산된) s에서 v까지의 거리보다 

# s에서 (최단거리로) u를 거쳐서 v로 가는 것이 더 짧다면

# d[v] 값을 이것으로 업데이트

if  d[v] > d[u] + w(u,v)

d[v] := d[u] + w(u,v)

previous[v] := u;


이 알고리즘에서 가장 햇갈리는 부분은 아마 다음에 거리를 계산할 노드 u를 선택하는 부분일 것이다. 시작 노드 s부터 방금 선택된 노드 u를 지나 다음 노드들 v까지의 거리는 d[v] := d[u] + w(u,v) 에 의해서 계산이 된다. 그 다음에 새로운 노드를 선택해서 동일한 과정을 진행해야 하는데, 이때 선택되는 새로운 노드는 extract_min()함수에 의해 결정된다. extract_min()함수는, 그 이름에서 알 수 있듯이, Q 노드 집합에서 s에서의 거리가 최소인 노드를 추출하는 함수이다. 


function extract_min(Q)

min = infinity;

next = null;

# d에 저장된 거리들 중에서 최소 거리인 노드 e를 찾음

for e in Q:

if  e not in S  && min < d[e]:

min = d[e];

next = e;

Q := Q - next;  #Q에서 next 노드 제거

return next;


extract_min()함수에서 선택된 노드는 Q 집합에서 S 집합으로 옮겨가게 된다. 여기서 S는 d[u]가 최단 경로로 판명된, 그래서 더이상 업데이트가 필요없는 노드들의 집합이다. 바꿔말하면 아직 S에 속하지 않은 노드들은 비록 d[u]가 계산되었다 하더라도 이것이 최단 거리인지는 아직 모르는 노드들인 것이다. 만약 시작 노드에서 모든 노드가 아닌 특정 노드 x까지의 최단 거리만 구하고 싶다면 extract_min()함수가 리턴하는 노드가 x일 때 알고리즘 수행을 멈추면 된다.


예제를 통해 지금까지 이야기한 것들을 정리해보자.

아래와 같은 그래프가 있다. 우리는 A에서 F까지의 최단 거리를 구하고 싶다고 하자. 초기의 S, Q, d 값들은 그림의 오른쪽과 같게 설정된다.






그림 1. 그래프 구조와 시작 상태


이제 루프를 돌면서 extract_min()로부터 현재 검사할 노드를 얻는다. 첫번째 루프에서는 당연히 시작 노드인 A가 리턴된다(d[A]만 값을 가지고 있으므로). 현재 노드 A(회색)에서 다음 노드들 B,C,D (붉은색)까지의 거리를 계산해 d 배열에 반영한다. 첫 번째 루프가 끝났을 때의 상태는 그림 2와 같다.



그림 2. 첫 번째 루프를 마쳤을 때의 상태


이제 두 번째 루프를 돌 때 어떤 일이 벌어지는지를 살펴보자. 먼저 extract_min()함수를 통해 다음에 검사할 노드를 알아내야 한다. S에 이미 속한 A노드를 제외한 나머지 노드들의 d값을 살펴보니 B가 최소값을 가지고 있다. 따라서 이번에는 B에서 다음 노드들까지의 거리를 계산한다. 이 그래프에서는 B에서 갈 수 있는 노드가 E밖에 없으므로 d[E]값만 계산하면 된다.



그림 3. 두 번째 루프를 마쳤을 때의 상태


이제 세 번째 루프를 돌 차례이다. 여기서 재미있는 일이 벌어진다. 이전과 마찬가지로 extract_min()함수를 이용해 다음에 검사할 노드를 찾는다. S에 있는 A, B노드를 제외하고 보니 D 노드가 가장 작은 값(d[D]=15)을 가지고 있다. 이제 D에서 이동할 수 있는 노드 C, F까지의 거리를 계산해보자. d[C]는 이미 30이라는 값을 가지고 있지만 d[D]+w[D,C] = 20이다. 즉, A에서 C로 직접 가는 것보다 A에서 D를 거쳐 C로 가는 것이 더 최단 거리인 것이다. 따라서 c[C]=20으로 업데이터한다. 또한 지금까지 infinty 값이었던 d[F]도 35로 업데이트된다. 여기서 주의할 점은 d[F]값을 계산하기는 했지만 아직 이것이 최단 거리인지는 모른다는 것이다. 이것을 보증하기 위해서는 extract_min()함수에서 F를 리턴할 때 까지 루프를 반복해야 한다.




그림 4. 세 번째 루프를 마쳤을 때의 상태


이제 다시 루프를 돌아보자. 이번에 검사할 노드는? 그렇다. extract_min()함수에서 C가 리턴될 것이다. C에서 갈 수 있는 노드는 F밖에 없다. d[F]는 이전 루프를 돌 때 이미 계산이 되었지만, 이번에 다시 계산해보니 C를 거쳐서 가면 거리가 25밖에 안되는 것을 알 수 있다(d[C] + w(C,F) = 25 ). 망설이지 말고 d[F]=25로 업데이트한다.


그림 5. 네 번째 루프를 마쳤을 때의 상태



이와 같은 과정을 계속 반복하게 되면 A에서 각 노드들까지의 최간 거리를 알 수 있게 된다.


시작 노드에서 모든 노드까지의 최단 거리를 알아내고자 할 때 위에서 설명한 다익스트라 알고리즘의 시간 복잡도는 O(n^2)이다. 이는 모든 노드에 대해서 최단 거리를 계산할 때 extract_min()함수에서 다시 한번 모든 노드를 선형 탐색하기 때문이다. 간선의 수가 적은 sparse graph의 경우에는 피보나치 힙을 이용해서 O(m + nlogn)까지 줄일 수 있다고 한다.



저작자 표시 비영리
신고
Creative Commons License
Creative Commons License

WRITTEN BY
trowind
자연어처리, 프로그래밍, 여행, 음식, 삶의 기록

받은 트랙백이 없고 , 댓글  2개가 달렸습니다.
  1. 정말 감사합니다. 많은 도움 되었구요 하나 오타가 있는 것 같아 혹시 몰라서 댓글 남기고 가봅니다.

    if e not in S && min < d[e]: 부분에서

    if e not in S && min > d[e]:로 수정을 하면 더 좋을 것 같습니다. ㅎㅎ
  2. 그렇네요. 어째 좀 이상하다 했습니다. 윗분 말씀대로 부등호 방향이 바뀌었네요.
    정말 좋은 포스팅 감사합니다.
secret