데이크스트라 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

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

알고리즘의 개요[편집]

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

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

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

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

의사코드(pseudocode)[편집]

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

 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)
10           S := S union {u}
11           for each edge (u,v) outgoing from u
12                  if d[v] > d[u] + w(u,v)             // (u,v)의 경감
13                        d[v] := d[u] + w(u,v)
14                        previous[v] := u                     //경로 추적할 때 쓰임//

만약 모든 v에 대해서가 아니라 특정한 s에서 t까지의 최단 거리만을 알고 싶다면 9번째 행에서 u = t일 때 종료하면 된다.

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]

이제 Ss에서 t까지의 최단경로 상에 있는 점들의 목록이 된다.

실행 시간[편집]

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

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

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

관련된 문제와 알고리즘[편집]

인터넷 라우팅에서 사용되는 OSPF(Open Shortest Path First) 방식의 프로토콜은 데이크스트라 알고리즘이 실제 현장에서 사용되는 좋은 사례이다.

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

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

참고 문헌[편집]

외부 고리[편집]

주석[편집]