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

잔글
점 → 꼭짓점, 간선 → 변. 그래프 이론그래프 용어와의 일관성.
잔글 (점 → 꼭짓점, 간선 → 변. 그래프 이론그래프 용어와의 일관성.)
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘'''({{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''로부터 다른 모든 점까지의꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다.
[[파일:Dijkstra's algorithm.svg|right|thumb|100px|예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.]]
 
== 알고리즘의 개요 ==
데이크스트라 알고리즘은 각각의 꼭짓점 ''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'']가 최단 경로의 비용을 나타내게 되었을 때 끝난다.
 
알고리즘은 과정이 끝날 때까지 점의꼭짓점의 집합 ''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)
5 u := previous[u]
 
이제 ''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> 시간이 된다.
 
만약 희소 그래프(sparse graph), 즉 <math>n^2</math>보다 훨씬 작은 개수의 간선만을변만을 갖는 그래프에 대해서는, [[인접 리스트(adjacency list)]]와 바이너리 [[힙 (자료 구조)|힙]] 또는 [[피보나치 힙으로힙]]으로 구현한 [[우선순위 큐(priority queue)]]를 이용해 데이크스트라 알고리즘을 더 효율적으로 구현할 수 있다. 바이너리[[이진 힙을힙]]을 이용하면 실행 시간은 <math>O((m+n)\log n)</math> 시간이 되고, [[피보나치 힙을힙]]을 통해 <math>O(m + n \log n)</math> 시간까지 개선할 수 있다.
 
== 관련된 문제와 알고리즘 ==
 
인터넷 [[라우팅]]에서 사용되는 [[OSPF]](Open Shortest Path First) 방식의 프로토콜은 데이크스트라 알고리즘이 실제 현장에서 사용되는 좋은 사례이다.
 
그래프의 가중치가 음수가 아니라고 가정하는 데이크스트라 알고리즘과는 달리, [[벨만벨먼-포드 알고리즘]]은 음수 가중치를 갖는 그래프에 대해서도 정확하게 동작한다. (단, 그래프에 음수 값을 갖는 순환 경로가 존재하지 않을 때)
 
목적지까지의 '거리'를 추정할 수 있는 방법이 있을 때, 데이크스트라 알고리즘의 변형인 [[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]], [[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://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html 데이크스트라 알고리즘의 애니메이션]
 
== 주석 ==
{{주석}}
 
<references />
 
[[분류:그래프 알고리즘]]