[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 40회차 미션

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.

방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다.

에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V^2)O(V2)의 시간복잡도를 가졌다. 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, O((V+E)logV)O((V+E)logV)(V는 정점의 개수, E는 한 정점의 주변 노드)의 시간복잡도를 가지게 되었다.[1]
O((V+E)logV)O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(VlogV)O(VlogV)의 시간이 필요하고[2], 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)O(ElogV)의 시간이 필요하기 때문이다.[3]

다익스트라 알고리즘이 하나의 노드로부터 최단경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘이다.[4]

다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다.

 

다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다)

1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.[5][6]

2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.

3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B][7]와 d[B][8]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.

4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.

5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.

6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.

7. "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.

8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

7번 단계에서, 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다. 모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 이때 제대로 구현된[9] 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다. 최단거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용해 고르면 된다. 이진 힙을 이용해 구현한 우선순위 큐의 경우 O(lg N) 출력에 O(lg N)이므로, 모든 노드 순회(O(N))보다 저렴하다. 우선순위 큐 구현에 피보나치 힙을 사용한 경우 삽입은 평균적으로 O(1), 출력에는 O(lg N)이 걸려 이론적으로 더 나은 시간복잡도를 얻을 수 있다. 단 이진 힙이 훨씬 간단하여 연산에 소요되는 시간이 빠르기 때문에, 엣지의 개수가 적은 경우에는 이진 힙을 사용하는 것이 더 나을 수 있다.

 

예를 들어, 다음과 같은 네트워크가 존재한다고 가정하자. 먼저, A 라우터의 목표는 F까지의 최단 거리 계산이며, 수단으로는 다익스트라 알고리즘을 활용한다. 이때, 각 데이터의 의미는 다음과 같다.

• S = 방문한 노드들의 집합

• d[N] = A → N까지 계산된 최단 거리

• Q = 방문하지 않은 노드들의 집합

1. 다익스트라 알고리즘은 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.

초기화가 실행된 후의 그래프.

• 출발지를 A로 초기화했기 때문에, 출발지와 출발지의 거리는 방문할 필요도 없이 당연히 0 값을 가진다. 즉, d[A]=0이 된다. (A노드를 방문한 것은 아니다.)

• 출발지를 제외한 모든 노드들도 아직 방문하지 않았기에, d[다른 노드]=무한이 된다.

• Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.

• S는 공집합 상태이다.

2. 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.

첫 루프를 마치고 난 뒤의 그래프.

• 루프의 시작은 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 즉, N을 '방문한다'는 의미이다.

• 이후, 모든 이웃 노드와의 거리를 측정하여 d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)이 계산된다.

• 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드에 기록된다. 따라서, d[B] = 10, d[C] = 30, d[D] =15로 값을 변경한다.

3. 첫 루프 이후의 그래프의 상태가 업데이트되는 방식

두 번째 루프를 마치고 난 뒤의 그래프.

이제 루프가 반복적으로 작동하는 방법을 설명한다. 밑의 그림들 또한 루프 안에서 알고리즘이 진행되는 순간들을 반복 설명한다.

• 이전에 설명했듯이, 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것으로 선택된다. 따라서, Q = {B, C, D, E, F} 중 B가 d[B] = 10으로 제일 작은 값을 가지므로, B를 방문하여 S에 추가하고 Q에서 제거한다.

• 이제, B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. B의 이웃 노드는 E 뿐이므로, d[E] 값이 무한에서 d[B]+(B와 E 사이의 값 20) = 30 으로 업데이트된다.[10] 여기서 d[B] 값을 더하는 이유는 출발지부터의 거리값을 재기 위해서다.

4. 더 빠른 경로를 발견한 경우

 

• 3번째 그림에서 설명했듯이, 이번에 선택·방문되는 노드는 D이다. Q의 원소 중에서 제일 낮은 d[N] 값을 가지고 있기 때문이다. 그래서, S에 D가 추가되어 있다.

• 이제 D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트한다. 특별한 상황은 d[C]의 값이 A를 방문할 때 이미 계산되어 30으로 정해져 있었으나, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 그러므로, d[C]의 값을 30에서 20으로 변경한다.

• d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 변경한다.

5. 또 다른 반복 루프 상황

 

• Q = {C,E,F}에서 d[C] = 20으로 C를 방문하여, S는 {A, B, D, C}가 되었다.

• 다시 이웃 노드와의 거리 계산을 해보니, 이번에는 (A→D) + (D→F) = 15 + 20 = 35보다, (A→D) + (D→C) + (C→F) = 15 + 5 + 5 = 25로 더 작은 값을 가지는 것이 발견되었다. d[F] = 25로 업데이트한다. 아쉽게도 그림이 더 이상 존재하지 않아서, 더 이상의 자세한 설명은 생략한다. 정말로 아쉽다. 머리에 쏙쏙 들어오는 설명이었다

이 일련의 과정이 반복되어 Q가 공집합이 되었다면, 남아 있는 데이터로 추론하여 최단 거리를 결정한다.

마지막 루프 이후,

• S = {A, B, D, C, F, E} (방문한 순서대로 정렬)

• d[A] = 0

• d[B] = 10

• d[C] = 20

• d[D] = 15

• d[E] = 30

• d[F] = 25

• Q = ∅

목적지가 F였으므로, A→D→C→F가 최단 경로이며, 거리는 25로 결정된다.

[1] 그래프가 희소한 경우에만 O(V^2)O(V2)보다 낫다. 피보나치 힙을 사용하는 경우 O(VlogV+E)O(VlogV+E)의 시간복잡도를 가진다.[2] 모든 노드 (O(V)O(V))에 대해 힙에서 최소값을 추출(O(logV)O(logV))[3] 각 노드마다 모든 이웃을 확인하는 것은 모든 edge를 확인하는 것과 같고 O(E)O(E), 매번 힙에서 최단 거리를 갱신O(logV)O(logV)해야 하기 때문이다[4] 각 노드마다 다익스트라 알고리즘을 적용해 모든 노드쌍들에 대한 최단거리를 구할 수도 있다[5] C++의 경우 std::numeric_limits::max, Python의 경우 타입에 따라 sys.maxint나 sys.float_info.max 등을 사용하면 안전한 값을 구할 수 있다. math.inf도 있다.[6] 참고로 자주 사용되는 int의 경우 2,147,483,647이 양의 최대값으로, 이걸 16진수로 표현하게 되면 0x7FFFFFFF이다. F가 7개. 이걸로도 모자랄 것 같으면 64비트 정수 타입을 쓰거나 아예 실수 타입을 써야 한다. 한편, INF+INF 등의 연산이 일어날 경우 오버플로우로 인해 오작동할 수 있으니 고려하여 INF 값을 책정할 것.[7] A를 거쳐서 B로 가는 최단 거리[8] 현재까지 알려진 B까지의 최단 거리[9] 우선순위 큐는 값을 받아 지정된 우선순위대로 내보낸다는 사양이 정의되어있을 뿐, 시간/공간 복잡도는 정의하지 않는다. 다만 제대로 구현된 경우 로그시간이 걸리는 것이 일반적.[10] 30은 무한값보다 당연히 작으므로 업데이트가 되는 것이다.

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG