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

틀 추가
잔글 (봇: 문단 이름 변경 (바깥 고리 → 외부 링크))
(틀 추가)
{{알고리즘 정보
|그림 = Dijkstra Animation.gif
|그림설명 = a와 b 사이의 최단 경로를 찾는 Dijkstra의 알고리즘. 가장 낮은 값을 가진 방문되지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.
|분류 = [[검색 알고리즘]]
|자료구조 = [[그래프 (자료 구조)|그래프]]
|최선 =
|평균 =
|최악 = <math>O(|E| + |V| \log|V|)</math>
|공간복잡도 =
}}
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘(=다익스트라 알고리즘)'''({{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''로부터 다른 모든 꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다
 
== 알고리즘의 개요 ==
데이크스트라 알고리즘은 각각의 꼭짓점 ''v''에 대해 ''s''에서 ''v''까지의 최단 거리 ''d''[''v'']를 저장하면서 작동한다. 알고리즘의 시작 시에 ''d''[''s'']=0이고, s가 아닌 다른 모든 꼭짓점 ''v''에 대해서는 ''d''[''v'']=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 ''d''[''v'']는 ''s''에서 ''v''까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
 
== 관련된 문제와 알고리즘 ==
인터넷 [[라우팅]]에서 사용되는 [[OSPF]](Open최단 Shortest경로 Path우선 First) 방식의 프로토콜은프로토콜]]은 데이크스트라 알고리즘이 실제 현장에서 사용되는 좋은 사례이다.
 
그래프의 가중치가 음수가 아니라고 가정하는 데이크스트라 알고리즘과는 달리, [[벨먼-포드 알고리즘]]은 음수 가중치를 갖는 그래프에 대해서도 정확하게 동작한다. (단, 그래프에 음수 값을 갖는 순환 경로가 존재하지 않을 때)
== 참고 문헌 ==
* 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.&nbsp;595–601.
 
== 외부 링크 ==
* [http://www.boost.org/libs/graph/doc/index.html Boost 그래프 라이브러리(BGL)]
* [http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm 대화형 구현]
 
 
[[분류:그래프 알고리즘]]