다익스트라 알고리즘
1. 개요
Dijkstra Algorithm
음의 가중치가 없는 그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.
그래프 방향의 유무는 상관 없으나, 간선(幹線, Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 말 그대로 최단'''거리'''에 관하여 논하는 문제이기 때문이다.
에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 $$O(V^2)$$의 시간복잡도를 가졌다. 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, $$O((V+E)logV)$$(V는 정점의 개수, E는 한 정점의 주변 노드)의 시간복잡도를 가지게 되었다.[1]
$$O((V+E)logV)$$의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 $$O(VlogV)$$의 시간이 필요하고[2], 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 $$O(ElogV)$$의 시간이 필요하기 때문이다.[3]
다익스트라 알고리즘이 하나의 노드로부터 최단경로를 구하는 알고리즘인 반면, 플로이드-워셜 알고리즘은 가능한 모든 노드쌍들에 대한 최단거리를 구하는 알고리즘이다.[4]
다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다.
2. 알고리즘의 실질적 이용
가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 고로 실질적 이용 예가 얼마나 많은지에 대해 더 이상의 자세한 설명은 생략한다.
예를 들어 루빅스 큐브를 푸는 프로그램을 다익스트라 알고리즘으로 만들 수 있고, 내비게이션에서 지도상의 각 도시들을 노드로, 도로들을 간선으로 갖는 그래프로 간주한다면, 두 도시를 잇는 가장 빠른 길을 찾는 문제를 이 알고리즘으로 해결할 수 있다. 또한 미로탐색 알고리즘으로도 사용할 수 있다. 라우팅에서도 OSPF 방식의 프로토콜의 경우가 좋은 예가 될 수 있다.
3. 알고리즘
다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다)
- 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.[5][6]
- 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
- A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B][7]와 d[B][8]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.
- 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.
- A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.
- A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.
- "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.
- 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.
7번 단계에서, 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다. 모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 이때 제대로 구현된[9] 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다. 최단거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용해 고르면 된다. 이진 힙을 이용해 구현한 우선순위 큐의 경우 O(lg N) 출력에 O(lg N)이므로, 모든 노드 순회(O(N))보다 저렴하다. 우선순위 큐 구현에 피보나치 힙을 사용한 경우 삽입은 평균적으로 O(1), 출력에는 O(lg N)이 걸려 이론적으로 더 나은 시간복잡도를 얻을 수 있다. 단 이진 힙이 훨씬 간단하여 연산에 소요되는 시간이 빠르기 때문에, 엣지의 개수가 적은 경우에는 이진 힙을 사용하는 것이 더 나을 수 있다.
3.1. 의사코드
GraphSourceprev[(node)]dist[(node)]function Dijkstra(Graph, Source): dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0-- prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined create vertex set Q //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작 for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화 if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!) dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값) prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화 add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가//요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함. while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로! u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작 remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거 for each neighbor v of u: // U의 이웃노드들과의 거리 측정 alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리 //= source to U + V to U = source to U if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우 dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈 prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈 return dist[], prev[] //계산된 거리값과 목적지를 리턴
3.2. 그림 설명
예를 들어, 다음과 같은 네트워크가 존재한다고 가정하자. 먼저, A 라우터의 목표는 F까지의 최단 거리 계산이며, 수단으로는 다익스트라 알고리즘을 활용한다. 이때, 각 데이터의 의미는 다음과 같다.
- S = 방문한 노드들의 집합
- d[N] = A → N까지 계산된 최단 거리
- Q = 방문하지 않은 노드들의 집합
[image]
초기화가 실행된 후의 그래프.
- 출발지를 A로 초기화했기 때문에, 출발지와 출발지의 거리는 방문할 필요도 없이 당연히 0 값을 가진다. 즉, d[A]=0이 된다. (A노드를 방문한 것은 아니다.)
- 출발지를 제외한 모든 노드들도 아직 방문하지 않았기에, d[다른 노드]=무한이 된다.
- Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
- S는 공집합 상태이다.
[image]
첫 루프를 마치고 난 뒤의 그래프.
- 루프의 시작은 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 즉, N을 '방문한다'는 의미이다.
- 이후, 모든 이웃 노드와의 거리를 측정하여 d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)이 계산된다.
- 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드에 기록된다. 따라서, d[B] = 10, d[C] = 30, d[D] =15로 값을 변경한다.
[image]
두 번째 루프를 마치고 난 뒤의 그래프.
이제 루프가 반복적으로 작동하는 방법을 설명한다. 밑의 그림들 또한 루프 안에서 알고리즘이 진행되는 순간들을 반복 설명한다.
- 이전에 설명했듯이, 방문할 노드는 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] 값을 더하는 이유는 출발지부터의 거리값을 재기 위해서다.
[image]
- 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로 변경한다.
[image]
- 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로 업데이트한다.
마지막 루프 이후,
- 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 = ∅
[1] 그래프가 희소한 경우에만 $$O(V^2)$$보다 낫다. 피보나치 힙을 사용하는 경우 $$O(VlogV+E)$$의 시간복잡도를 가진다.[2] 모든 노드 ($$O(V)$$)에 대해 힙에서 최소값을 추출($$O(logV)$$)[3] 각 노드마다 모든 이웃을 확인하는 것은 모든 edge를 확인하는 것과 같고 $$O(E)$$, 매번 힙에서 최단 거리를 갱신$$O(logV)$$해야 하기 때문이다[4] 각 노드마다 다익스트라 알고리즘을 적용해 모든 노드쌍들에 대한 최단거리를 구할 수도 있다[5] C++의 경우
std::numeric_limits::maxsys.maxintsys.float_info.maxmath.inf도 있다.