데이크스트라 알고리즘: 두 판 사이의 차이

위키백과, 우리 모두의 백과사전.
내용 삭제됨 내용 추가됨
편집 요약 없음
잔글 점 → 꼭짓점, 간선 → 변. 그래프 이론그래프 용어와의 일관성.
1번째 줄: 1번째 줄:
'''데이크스트라 알고리즘'''(Dijkstra algorithm) 또는 '''다익스트라 알고리즘'''은 어떤 간선도 음수 값을 갖지 않는 [[그래프|방향 그래프]]에서 주어진 출발점과 도착점 사이의 [[최단 경로 문제]]를 푸는 알고리즘이다. 이름은 [[네덜란드]]의 [[컴퓨터 과학|컴퓨터과학자]] [[에츠허르 데이크스트라]]의 이름에서 유래했다. 예컨대 어떤 그래프에서, 점들이 각각 도시를 나타내고, 연결선들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘'''({{llang|en|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''로부터 다른 모든 점까지의 최단 경로를 계산하는 데도 사용할 수 있다.
데이크스트라 알고리즘은 방향이 주어진 [[가중 그래프]](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''로부터 다른 모든 꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다
[[파일:Dijkstra's algorithm.svg|right|thumb|100px|예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.]]
[[파일:Dijkstra's algorithm.svg|right|thumb|100px|예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.]]

== 알고리즘의 개요 ==
== 알고리즘의 개요 ==
데이크스트라 알고리즘은 각각의 ''v''에 대해 ''s''에서 ''v''까지의 최단 거리 ''d''[''v'']를 저장하면서 작동한다. 알고리즘의 시작 시에 이 값은 ''s''에 대해서는 0이고, (''d''[''s'']=0) 다른 모든 점에 대해서는 무한대(∞) 값으로 놓아 다른 점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 ''d''[''v'']는 ''s''에서 ''v''까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
데이크스트라 알고리즘은 각각의 꼭짓점 ''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'']를 새로운 값으로 바꾼다.
데이크스트라 알고리즘은 ''' 경감'''('''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'']가 최단 경로의 비용을 나타내게 되었을 때 끝난다.
경감 연산은 모든 (''u'', ''v'')에 대해 한번씩 경감이 적용되어 모든 ''d''[''v'']가 최단 경로의 비용을 나타내게 되었을 때 끝난다.


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


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

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


1 '''function''' Dijkstra(G, w, s)
1 '''function''' Dijkstra(G, w, s)
40번째 줄: 40번째 줄:
5 u := previous[u]
5 u := previous[u]


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


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

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


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


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


== 관련된 문제와 알고리즘 ==
== 관련된 문제와 알고리즘 ==

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


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


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


== 참고 문헌 ==
== 참고 문헌 ==

* E. W. Dijkstra: ''A note on two problems in connexion with graphs''. In: ''Numerische Mathematik''. 1 (1959), S. 269–271
* 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]], [[Ronald L. Rivest]], 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.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], 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.


== 외부 고리 ==
== 바깥 고리 ==
* [http://en.wikisource.org/wiki/Dijkstra%27s_algorithm 여러 가지 구현]
* [http://en.wikisource.org/wiki/Dijkstra%27s_algorithm 여러 가지 구현]
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html 데이크스트라 알고리즘의 애니메이션]
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html 데이크스트라 알고리즘의 애니메이션]
70번째 줄: 67번째 줄:


== 주석 ==
== 주석 ==
{{주석}}

<references />


[[분류:그래프 알고리즘]]
[[분류:그래프 알고리즘]]

2014년 12월 13일 (토) 12:26 판

컴퓨터 과학에서, 데이크스트라 알고리즘(영어: 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에서 시작하는 모든 변에 대해 경감 연산을 행한다.

의사코드

아래 알고리즘 의사코드에서 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까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.

실행 시간

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

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

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

관련된 문제와 알고리즘

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

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

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

참고 문헌

바깥 고리

주석