데이크스트라 알고리즘

데이크스트라 알고리즘

a와 b 사이의 최단 경로를 찾는 Dijkstra의 알고리즘. 가장 낮은 값을 가진 방문되지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.
분류	검색 알고리즘
자료 구조	그래프
최악 시간복잡도	$O(|E|+|V|\log |V|)$

컴퓨터 과학에서, 데이크스트라 알고리즘(=다익스트라 알고리즘)(영어: Dijkstra algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라의 이름에서 유래했다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.

데이크스트라 알고리즘은 방향이 주어진 가중 그래프(weighted graph) G와 출발점 s를 입력으로 받는다. 그래프 G의 모든 꼭짓점들의 집합을 V라 하고, 그래프의 변을 출발점 u와 도착점 v의 순서쌍 (u, v)로 표현한다. G의 모든 변들의 집합을 E라 하고, 변들의 가중치는 함수 w: E → [0, ∞]로 표현한다. 이때 가중치 w(u, v)는 꼭짓점 u에서 꼭짓점 v로 이동하는 데 드는 비용(시간, 거리 등)이 된다. 경로의 비용은 경로 사이의 모든 변들의 가중치의 합이 된다. 데이크스트라 알고리즘은 V의 임의의 꼭짓점의 쌍 s와 t가 있을 때 s에서 t로 가는 가장 적은 비용이 드는 경로(최단 경로)를 찾는다. 이 알고리즘은 주어진 출발점 s로부터 다른 모든 꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다

알고리즘의 개요

데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.

데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.

경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다.

알고리즘은 과정이 끝날 때까지 꼭짓점의 집합 S와 Q를 저장한다. S는 d[v]가 최단 경로의 비용임이 이미 알려진 꼭짓점 v의 집합이고 Q는 나머지 꼭짓점들의 집합을 가리킨다. S는 공집합에서 시작하여 매 단계마다 Q에서 S로 꼭짓점들이 하나씩 옮겨 오며, 이때 옮겨 오는 꼭짓점들은 d[u]가 가장 낮은 값을 갖는 꼭짓점 u로 정해진다. u가 S로 옮겨 오면, 알고리즘은 u에서 시작하는 모든 변에 대해 경감 연산을 행한다.

예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.

의사코드

아래 알고리즘 의사코드에서 u := Extract_Min(Q)는 꼭짓점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 꼭짓점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.

 1   function Dijkstra(G, w, s)
 2      for each vertex v in V[G]                        // 초기화
 3            d[v] := infinity
 4            previous[v] := undefined
 5      d[s] := 0                                                     //덮어쓰기
 6      S := empty set
 7      Q := set of all vertices
 8      while Q is not an empty set                      // 알고리즘의 실행
 9           u := Extract_Min(Q)                                //집합 Q에서 d[u]가 최소인 u를 찾아 빼냄
10           S := S union {u}                                      //빼낸 u를 S에 삽입
11           for each v with edge (u,v) defined
12                  if d[v] > d[u] + w(u,v)
13                        d[v] := d[u] + w(u,v)              // 변(u,v)의 경감
14                        previous[v] := u                     //경로 추적할 때 쓰임//

만약 s에서 모든 v에 까지의 최소 경로를 찾는 것이 아니라, s에서 특정 꼭짓점 t까지의 최단 거리만을 알고 싶다면 8번째 행에 $u\neq t$의 조건을 추가하면 된다.

previous[]가 구해지면, 이를 이용해 다음과 같이 s에서 t까지의 최단 경로를 얻을 수 있다.

1 S := empty sequence
2 u := t
3 while defined u
4       insert u to the beginning of S
5       u := previous[u]

이제 S는 s에서 t까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.

실행 시간

$m$개의 변과 $n$개의 꼭짓점을 가진 그래프에 대해 대문자 O 표기법으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다.

가장 간단한 구현으로, Q의 집합을 연결 리스트나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현했을 때 실행 시간은 $O(n^{2})$ 시간이 된다.

만약 희소 그래프(sparse graph), 즉 $n^{2}$보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트와 바이너리 힙 또는 피보나치 힙으로 구현한 우선순위 큐를 이용해 데이크스트라 알고리즘을 더 효율적으로 구현할 수 있다. 이진 힙을 이용하면 실행 시간은 $O((m+n)\log n)$ 시간이 되고, 피보나치 힙을 통해 $O(m+n\log n)$ 시간까지 개선할 수 있다.

관련된 문제와 알고리즘

인터넷 라우팅에서 사용되는 최단 경로 우선 프로토콜은 데이크스트라 알고리즘이 실제 현장에서 사용되는 좋은 사례이다.

그래프의 가중치가 음수가 아니라고 가정하는 데이크스트라 알고리즘과는 달리, 벨먼-포드 알고리즘은 음수 가중치를 갖는 그래프에 대해서도 정확하게 동작한다. (단, 그래프에 음수 값을 갖는 순환 경로가 존재하지 않을 때)

목적지까지의 '거리'를 추정할 수 있는 방법이 있을 때, 데이크스트라 알고리즘의 변형인 A* 알고리즘은 탐색해야 할 그래프의 크기를 줄이는 방법으로 더 빠르게 경로를 찾을 수 있다.

참고 문헌

• E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271
• Thomas H. Cormen, Charles E. Leiserson, 로널드 라이베스트, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp. 595–601.

외부 링크

• 여러 가지 구현
• 데이크스트라 알고리즘의 애니메이션
• Boost 그래프 라이브러리(BGL)
• 대화형 구현