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

번역:en:Dijkstra's algorithm, 주석처리한 단어는 대체할 단어를 아시면 바꿔주십시오
잔글 (ISBN 매직 링크 제거)
(번역:en:Dijkstra's algorithm, 주석처리한 단어는 대체할 단어를 아시면 바꿔주십시오)
{{알고리즘 정보
|그림 = Dijkstra Animation.gif
|그림설명 = a와 b 사이의 최단 경로를 찾는 Dijkstra의 알고리즘. 가장 낮은 값을 가진 방문되지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.
|분류 = [[검색 알고리즘]]
|그림 = [[파일:Dijkstra Animation.gif|데이크스트라 알고리즘 실행]]
|그림설명 = ''a''와 ''b'' 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다.
|자료구조 = [[그래프 (자료 구조)|그래프]]
|최악 = <math>O(|E| + |V| \log|V|)</math>
|최선 =
|평균 =
|최악 = <math>O(|E| + |V| \log|V|)</math>
|공간복잡도 =
}}
{{그래프 검색 알고리즘}}
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘(=다익스트라 알고리즘)'''({{llang|en|Dijkstra algorithm}})은 어떤 변도 음수 가중치를 갖지 않는 [[유향 그래프]]에서 주어진 출발점과 도착점 사이의 [[최단 경로 문제]]를 푸는 알고리즘이다. 이름은 [[네덜란드]]의 [[컴퓨터 과학|컴퓨터과학자]] [[에츠허르 데이크스트라]]의 이름에서 유래했다. 예컨대 어떤 [[그래프]]에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.
[[컴퓨터 과학]]에서, '''데이크스트라 알고리즘(=다익스트라 알고리즘)'''({{llang|en|Dijkstra algorithm}})은 도로 교통망 같은 곳에서 나타날 수 있는 [[그래프 (자료 구조)|그래프]]에서 꼭짓점 간의 [[최단 경로 문제|최단 경로]]를 찾는 [[알고리즘]]이다. 이 알고리즘은 [[컴퓨터 과학자]] [[에츠허르 데이크스트라]]가 1956년에 고안했으며 삼 년 뒤에 발표했다.<ref>{{웹 인용|url=http://amturing.acm.org/award_winners/dijkstra_1053701.cfm |title=Edsger Wybe Dijkstra |last=Richards |first=Hamilton |website=A.M. Turing Award |publisher=Association for Computing Machinery |access-date=October 16, 2017 |quote=At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?}}</ref><ref name="Dijkstra Interview">{{저널 인용|first=Phil |last=Frana |title=An Interview with Edsger W. Dijkstra|journal=Communications of the ACM|date=August 2010|volume=53|issue=8|pages=41–47 |doi=10.1145/1787234.1787249}}</ref><ref name="Dijkstra1959">{{저널 인용| authorlink = 에츠허르 데이크스트라 | first1 = E. W. | last1 = Dijkstra | url= http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf | title = A note on two problems in connexion with graphs | journal = Numerische Mathematik | volume = 1 | year = 1959 | pages = 269–271 | ref = harv | doi = 10.1007/BF01386390}}</ref>
 
이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만,{{r|Dijkstra1959}} 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 [[최단 경로 트리]]를 만드는 것이다.
데이크스트라 알고리즘은 방향이 주어진 [[가중 그래프]](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''로부터 다른 모든 꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다
 
그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다.<ref name="mehlhorn">{{서적 인용|last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn|first2=Peter |last2=Sanders|author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |publisher=Springer |year=2008 |chapter=Chapter 10. Shortest Paths |chapterurl=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ShortestPaths.pdf |isbn=978-3-540-77977-3 |doi=10.1007/978-3-540-77978-0}}</ref>{{rp|196–206}} 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 [[그래프]]에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 [[라우팅 프로토콜]]에서 널리 이용되며, 특히 [[IS-IS]] (Intermediate System to Intermediate System)와 [[OSPF]](Open Shortest Path First)에서 주로 사용된다. 또한 데이크스트라 알고리즘은 [[존슨 알고리즘]] 같은 알고리즘의 [[서브루틴]]으로 채택되었다.
== 알고리즘의 개요 ==
데이크스트라 알고리즘은 각각의 꼭짓점 ''v''에 대해 ''s''에서 ''v''까지의 최단 거리 ''d''[''v'']를 저장하면서 작동한다. 알고리즘의 시작 시에 ''d''[''s'']=0이고, s가 아닌 다른 모든 꼭짓점 ''v''에 대해서는 ''d''[''v'']=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 ''d''[''v'']는 ''s''에서 ''v''까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
 
데이크스트라의 원래 알고리즘은 [[우선순위 큐|최소 우선 큐]]를 사용하지 않았기 때문에 [[시간 복잡도]]가 <math>O(|V|^2)</math> (<math>|V|</math>는 꼭짓점의 개수이다)이다. 이 알고리즘의 개념은 {{괄호 없는 하버드 인용|Leyzorek|Gray|Johnson|Ladew|1957}}에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 [[피보나치 힙]]으로 수행되며 시간복잡도는 {{괄호 없는 하버드 인용|Fredman|Tarjan|1984}} 때문에 <math>O(|E|+|V|\log|V|)</math> (<math>|E|</math>는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 [[유향 그래프]]에서의 단일 소스 [[최단 경로 문제|최단 경로 알고리즘]] 중 [[점근 계산 복잡도|점근적]]으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 {{slink||세분화된 변형}}으로 개선할 수 있다.
데이크스트라 알고리즘은 '''변 경감'''('''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'']를 새로운 값으로 바꾼다.
 
어떤 분야, 특히 [[인공 지능]] 분야에서, 데이크스트라 알고리즘이나 그 변형은 '''균일 비용 탐색'''으로 알려져 있으며 [[최상 우선 탐색]]의 일반적인 아이디어의 예시로 공식화 되어있다.<ref name="felner">{{콘퍼런스 인용|first=Ariel |last=Felner |title=Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm |conference=Proc. 4th Int'l Symp. on Combinatorial Search |year=2011 |url=http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4017/4357}}</ref>
경감 연산은 모든 변 (''u'', ''v'')에 대해 한번씩 경감이 적용되어 모든 ''d''[''v'']가 최단 경로의 비용을 나타내게 되었을 때 끝난다.
 
== 역사 ==
알고리즘은 과정이 끝날 때까지 꼭짓점의 집합 ''S''와 ''Q''를 저장한다. ''S''는 ''d''[''v'']가 최단 경로의 비용임이 이미 알려진 꼭짓점 ''v''의 집합이고 ''Q''는 나머지 꼭짓점들의 집합을 가리킨다. ''S''는 공집합에서 시작하여 매 단계마다 ''Q''에서 ''S''로 꼭짓점들이 하나씩 옮겨 오며, 이때 옮겨 오는 꼭짓점들은 ''d''[''u'']가 가장 낮은 값을 갖는 꼭짓점 ''u''로 정해진다. ''u''가 ''S''로 옮겨 오면, 알고리즘은 ''u''에서 시작하는 모든 변에 대해 경감 연산을 행한다.[[파일:Dijkstra's algorithm.svg|right|thumb|100px|예제 그래프에 대해 데이크스트라 알고리즘을 수행하는 모습. 두 개의 경감 연산을 보여주고 있다.]]
{{인용문5|[[로테르담]]에서 [[흐로닝언]]까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길은 무엇일까요? 이것은 제가 이십 분 동안 생각해낸 [[최단 경로 문제|최단 거리를 찾는 알고리즘]]입니다. 어느 날 아침에 저는 제 약혼녀와 [[암스테르담]]에서 쇼핑을 하고 있었고, 지쳤었기 때문에 카페 테라스에 앉아서 커피를 마시면서 그 문제에 대해서 생각하다가 최단 거리를 찾는 알고리즘을 고안했습니다. 제가 말했듯이, 이것은 이십 분 짜리 발명품입니다. 사실, 이 알고리즘은 삼 년 뒤인 59년에 발표했습니다. 그 간행물을 여전히 읽을 수 있습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다.<!--What is the shortest way to travel from [[Rotterdam]] to [[Groningen]], in general: from given city to given city. [[Shortest path problem|It is the algorithm for the shortest path]], which I designed in about twenty minutes. One morning I was shopping in [[Amsterdam]] with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.-->|에츠허르 데이크스트라, Philip L과의 인터뷰에서. Frana, Communications of the ACM, 2001<ref name="Dijkstra Interview"/>}}
데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다.<ref>{{웹 인용|title=ARMAC|url=http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html|website=Unsung Heroes in Dutch Computing History|date=2007|archiveurl=https://web.archive.org/web/20131113021126/http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html|archivedate=13 November 2013|deadurl=yes|df=dmy-all}}</ref> 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 (컴퓨터가 만들어낸)해법을 둘 다 선택하는 것이었다. 그는 최단 거리 알고리즘을 고안하고, 이후 ARMAC에서 약간 단순화된 네덜란드 도시 64개(도시의 숫자를 표시하기 위해서 6 비트만 필요하도록 64를 선정했다)의 교통 지도에 대해서 수행했다.<ref name="Dijkstra Interview"/> 일 년 뒤, 데이크스트라는 기관의 다음 컴퓨터를 작업하던 하드웨어 엔지니어들의 문제를 직면했다: 기계의 후면 패널에 있는 핀을 연결 할 때 필요한 전선의 갯수를 최소화 하는 것이다. 그 해법으로, [[프림 알고리즘|프림 최소 신장 트리 알고리즘]]으로 알려진 알고리즘을 재발견 했다(이전에는 [[Vojtěch Jarník|Jarník]]에 의해 알려져 있었고, 또한 프림에 의해 재발견 되었었다).<ref name="EWD841a">{{인용| last1 = Dijkstra | first1 =Edsger W. | title = Reflections on "A note on two problems in connexion with graphs | url = https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD841a.PDF}}</ref><ref>{{인용|first=Robert Endre|last=Tarjan|authorlink=로버트 타잔|title=Data Structures and Network Algorithms|series=CBMS_NSF Regional Conference Series in Applied Mathematics|volume=44|year=1983|publisher=Society for Industrial and Applied Mathematics|page=75|quote=The third classical minimum spanning tree algorithm was discovered by Jarník and rediscovered by Prim and Dikstra; it is commonly known as Prim's algorithm.}}</ref> 데이크스트라는 이 알고리즘을 프림이 발표한 지 2년 뒤이고 Jarník이 발표한 지 29년 뒤인 1959년에 발표했다.<ref>{{저널 인용|last1=Prim|first1=R.C.|title=Shortest connection networks and some generalizations|journal=Bell System Technical Journal|date=1957|volume=36|pages=1389–1401|doi=10.1002/j.1538-7305.1957.tb01515.x|url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf|archiveurl=https://web.archive.org/web/20170718230207/http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Prim1957.pdf|archivedate=18 July 2017|deadurl=no|df=dmy-all}}</ref><ref>V. Jarník: ''O jistém problému minimálním'' [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp.&nbsp;57–63. (in Czech)</ref>
 
== 의사코드알고리즘 ==
[[파일:Dijkstras progress animation.gif|thumb|[[로봇공학|로봇]] [[모션 계획]] 문제에서 데이크스트라 알고리즘이 시작점(좌측 하단, 빨간색)에서 도착점(우측 상단, 초록색)까지의 경로를 찾는 도해. 빈 꼭짓점은 "시험" 집합("미방문" 꼭짓점들의 집합)을 나타낸다. 채워진 꼭짓점은 방문한 꼭짓점으로, 색은 거리를 나타낸다: 초록색이 될 수록 더 가깝다는 의미이다. 다른 방향으로 있는 꼭짓점들은 균일하게 탐색되며, 데이크스트라 알고리즘이 [[균일 휴리스틱|휴리스틱]]을 0과 같게 사용하기 때문에 원형 [[파면]]으로 적거나 많게 나타난다.]]
아래 알고리즘 [[의사코드]]에서 u := Extract_Min(Q)는 꼭짓점의 집합 ''Q''에서 가장 작은 ''d''[''u'']값을 찾은 다음 그 꼭짓점 ''u''를 ''Q''에서 제거한 후 반환하는 함수를 가리킨다.
 
시작할 꼭짓점은 '''초기점'''으로, '''꼭짓점 ''Y''의 거리'''를 '''초기점'''에서 ''Y''까지의 거리로 정의한다. 데이크스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 '''변 경감'''('''edge relaxation''')이라고 한다.
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번째 행에 <math>u\neq t</math>의 조건을 추가하면 된다.
 
# 모든 꼭짓점을 미방문 상태로 표시한다. ''미방문 집합''이라는 모든 미방문 꼭짓점의 집합을 만든다.
previous[]가 구해지면, 이를 이용해 다음과 같이 ''s''에서 ''t''까지의 최단 경로를 얻을 수 있다.
# 모든 꼭짓점에 시험적 거리 값을 부여한다: 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정한다. 초기점을 현재 위치로 설정한다.
# 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 ''시험적'' 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 ''시험적'' 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 ''A''의 <!--시험적 ((이 거리는 '''시험적 거리가 아니기''' 때문에 주석 처리 했습니다.. 이 값은 인접 꼭짓점을 방문할 때 바뀔 수 없습니다.. 따라서 이것을 시험적이라고 부르는 것은 아직 바뀔 수 있다는 것을 의미하므로 혼동을 줄 수 있습니다))-->거리가 6이라고 표시되었고, 인접 꼭짓점 ''B''으로 연결되는 변의 길이가 2라고 한다면, ''A''를 통한 ''B''의 거리는 6 + 2 = 8이 될 것이다. B가 이전에 거리가 8보다 크다고 표시되었었다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
# 만약 현재 노드에 인접한 모든 미방문 꼭짓점을 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 ''미방문 집합''에서 제거한다. 방문한 꼭짓점은 이후에는 다시 검사하지 않는다.
<!-- 이 거리는 마지막이며 최솟값으로 기록된다. ((거리는 큐에서 꺼내어 다루고 있던 현재 위치에 대해서 마지막이기 때문에 주석 처리했습니다.. 이 거리는 인접 꼭짓점을 방문하는 동안 줄어들 수 없습니다.. 하지만 현재 꼭짓점은 이 단계 전까지는 미방문 상태입니다. 이 점은 일관적이지 않으며 혼란을 줍니다.)) -->
<!-- # 시험적 거리가 가장 작은 다음 미방문 꼭짓점으로 이동하고 위의 인접 꼭짓점을 계산하고 방문한 상태로 표시하는 단계를 반복한다. ((이 줄은 아래의 내용과 동일하며, 무한루프를 형성하고, 설명이 더 모호합니다)) -->
# 도착점이 방문한 상태로 표시되거나 (특정 두 꼭짓점 사이의 경로를 계획하고 있을 때) ''미방문 집합''에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면(완전 순회를 계획중일 때. 이 현상은 초기점과 나머지 미방문 집합 간에 연결이 없을 때 일어난다), 멈춘다. 알고리즘을 종료한다.
# 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 "현재 위치"로 선택하고 3단계로 되돌아간다.
 
경로를 계획하고 있을 때, 사실은 위에서 했던 것처럼 도착점이 "방문"한 상태가 될 때 까지 기다릴 필요가 없다: 도착점이 "미방문" 꼭짓점들 중 가장 시험적 거리가 작아지면 (그리고 다음 "현재 위치"로 선택될 수 있다면) 알고리즘을 종료할 수 있다.
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''까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.
:'''''참고:''' 이 문단에서는 이해를 돕기 위해서 '''교차로''', '''도로''' 그리고 '''지도'''라는 용어를 사용했지만, 공식적인 용어는 각각 '''꼭짓점''', '''변''' 그리고 '''그래프'''이다.''
 
도심 지도에서 ''시작점''과 ''목적지''의 두 [[교차로]] 간의 ''가장 짧은 거리''를 찾는다고 가정하자. 데이크스트라 알고리즘은 지도에 있는 다른 모든 교차로의 거리(현 위치에서)를 ''무한대''로 표시해둔다. 이 표시는 실제로 거리가 무한이라는 뜻이 아니라, 이 교차로에 가본 적이 없다는 것을 표시하기 위해서이다: 이 방법의 일부 변형은 단순히 교차로의 거리를 ''미표시'' 상태로 놔둔다. 이제 반복할 때 마다 ''현 위치''를 선택한다. 첫 번째 반복에서, 현 위치는 시작점이며, 거리(교차로의 표시)는 ''0''이다. 그 다음의 반복에서 현 위치는 시작점에서 ''가본 적 없으면서 가장 가까운 교차로''가 된다(이 교차로는 찾기 쉬울 것이다).
 
현 위치에서 직접적으로 연결된 가본 적 없는 교차로의 거리를 ''갱신''한다. 이 단계는 현 위치에서 가본 적 없는 교차로까지의 거리와 현 위치의 값을 ''더한'' 값이 현재 거리 보다 작을 때, 가본 적 없는 교차로의 [[그래프 번호매김|거리를 이 값(합)으로 바꾼다]]. 결과적으로, 그 교차로는 현 위치를 통과해 가는 경로가 이전 경로보다 짧을 경우에 거리를 바꾼다. 최단 경로를 찾기 편리하게 하려면 교차로의 거리를 붙였다면/바꿨다면, 연필로 도로에 거리를 바꾼 교차로를 향하는 화살표를 도로에 그리고 그 방향을 향하는 다른 화살표를 지운다. 모든 [[인접 (그래프 이론)|인접 교차로]]의 거리를 갱신하고 나면 현 위치를 ''방문''했다고 표시하고, 방문한 적 없는 교차로 중 (시작점에서) 가장 거리가 짧은 교차로를 선택한다. 방문 했다고 표시한 교차로는 시작점에서 가는 가장 짧은 경로가 표시되어 있을 것이며 다시 방문하거나 돌아갈 일은 없다.
 
인접한 교차로를 최단 거리로 갱신하고 현 교차로에 방문한 표시를 하고 가장 방문한 적 없는 가까운 교차로로 이동하는 과정을 목적지에 방문 표시가 될 때 까지 계속한다. 목적지에 한 번 방문 표시가 되면 (비단 목적지 뿐만 아니라 어떤 교차로에도 해당한다) 시작점에서 최단 경로가 결정되었고, ''화살표를 거슬러서 길을 되돌아갈 수 있다''. 알고리즘의 수행에서, 이 부분은(알고리즘이 목적지 노드에 도착한 이후에) 목적지 꼭짓점의 부모 노드를 쫓아 시작점으로 감으로 수행된다. 이것이 계속해서 각각의 노드의 부모 노드를 쫓아가고 있었던 이유이다.
 
이 알고리즘은 모두가 예측하는 것처럼 목적지를 향해서 "조사"하려는 시도를 하지 않는다. 대신에, 다음 "현 위치"를 결정하는 유일한 고려사항은 시작점에서의 거리 뿐이다. 이 알고리즘은 따라서 시작점에서 뻗어나가기 때문에, 목적지까지 가는 최단 경로보다 짧은 거리에 있는 모든 꼭짓점을 고려한다. 이렇게 이해한다면, 알고리즘은 필연적으로 최단 경로를 찾을 수 밖에 없다. 하지만 이 특징은 데이크스트라 알고리즘의 약점 중 하나를 나타낸다: 일부 위상에서 상대적으로 느리다는 점이다.
 
== 의사 코드 ==
 
다음 알고리즘에서, 코드 {{모노|u ← vertex in ''Q'' with min dist[u]}}는 꼭짓점 집합 {{모노|<var>Q</var>}}에서 가장 작은 {{모노|dist[<var>u</var>]}} 값을 가지는 꼭짓점 {{모노|<var>u</var>}}를 찾는다. {{모노|length(<var>u</var>, <var>v</var>)}}는 두 인접한 꼭짓점인 {{모노|<var>u</var>}}와 {{모노|<var>v</var>}}를 연결하는 변의 길이 (둘 간의 거리)를 반환한다. 18번째 줄의 변수 {{모노|<var>alt</var>}}는 루트 꼭짓점에서 {{모노|<var>u</var>}}를 통해서 인접 꼭짓점 {{모노|<var>v</var>}}까지 가는 경로의 길이이다. 이 경로가 현재 {{모노|<var>v</var>}}에 대해서 기록된 최단 경로보다 짧다면, 현재 경로를 이 {{모노|<var>alt</var>}} 경로로 대체한다. {{모노|prev}} 배열은 소스까지 최단 경로를 찾기 위한 소스 그래프의 "다음" 꼭짓점을 나타내는 배열이다.
[[파일:DijkstraDemo.gif|thumb|유클리드 거리에 기반한 데이크스트라 알고리즘의 시연이다. 빨간색 선은 최단 경로이다. 다시 말해, ''u''와 [''u'']를 연결하는 선이다. 파란 선은 변 경감이 이루어지는 위치를 나타낸다. 즉, ''v''와 ''Q''에 있는 꼭짓점 ''u''를 연결하는 선으로, 소스에서 ''v''까지 가는 더 짧은 경로를 나타낸다.]]
 
1 '''function''' Dijkstra(''Graph'', ''source''):
2
3 create vertex set Q
4
5 '''for each''' vertex ''v'' in ''Graph'': ''// 초기화''
6 dist[''v''] ← INFINITY ''// 소스에서 v까지의 아직 모르는 길이''
7 prev[''v''] ← UNDEFINED ''// 소스에서 최적 경로의 이전 꼭짓점''
8 add ''v'' to ''Q'' ''// 모든 노드는 초기에 Q에 속해있다 (미방문 집합)''
9
10 dist[''source''] ← 0 ''// 소스에서 소스까지의 길이''
11
12 '''while''' ''Q'' is not empty:
13 ''u'' ← vertex in ''Q'' with min dist[u] ''// 최소 거리를 갖는 꼭짓점''
14 ''// 을 가장 먼저 선택한다''
15 remove ''u'' from ''Q''
16
17 '''for each''' neighbor ''v'' of ''u'': ''// v는 여전히 Q에 있다.''
18 ''alt'' ← dist[''u''] + length(''u'', ''v'')
19 '''if''' ''alt'' < dist[''v'']: ''// v 까지의 더 짧은 경로를 찾았을 때''
20 dist[''v''] ← ''alt''
21 prev[''v''] ← ''u''
22
23 '''return''' dist[], prev[]
 
만약 {{모노|<var>source</var>}}에서 {{모노|<var>target</var>}}까지의 최단 경로만을 구하고 싶다면, 15번째 줄에 {{모노|<var>u</var> {{=}} <var>target</var>}}을 추가해서 종료시킬 수 있다.
그리고 나서는 {{모노|<var>source</var>}}에서 {{모노|<var>target</var>}}까지의 최단 경로를 역방향 반복을 통해서 읽을 수 있다:
 
1 ''S'' ← empty sequence
2 ''u'' ← ''target''
3 '''while''' prev[''u''] is defined: ''// 스택 S로 최단 경로를 만든다''
4 insert ''u'' at the beginning of ''S'' ''// 꼭짓점을 스택에 넣는다''
5 ''u'' ← prev[''u''] ''// target에서 source로 이동한다''
6 insert ''u'' at the beginning of ''S'' ''// source를 스택에 넣는다''
 
그러면 수열 {{모노|<var>S</var>}}는 {{모노|<var>source</var>}}에서 {{모노|<var>target</var>}}으로 가는 경로에 있는 꼭짓점의 목록이거나 경로가 존재하지 않다면 빈 수열이다.
 
더 일반적인 문제는 {{모노|<var>source</var>}}에서 {{모노|<var>target</var>}}까지 가는 모든 최단 경로를 찾는 것이다(같은 길이를 가지는 다른 경로가 있을 수 있다). 그러면, 각각의 {{모노|prev[]}}에 꼭짓점 하나만을 저장하는 것이 아니라, 경감 조건을 만족하는 모든 꼭짓점을 모두 저장할 수 있다. 예를 들어, {{모노|<var>r</var>}}과 {{모노|<var>source</var>}}가 둘 다 {{모노|<var>target</var>}}으로 연결되어 있고 (변의 비용이 두 경우 모두 다 같아서) 둘 다 {{모노|<var>target</var>}}으로 가는 다른 최단 경로에 있다면, {{모노|prev[<var>target</var>]}}에 {{모노|<var>r</var>}}과 {{모노|<var>source</var>}} 모두 추가해야 한다. 알고리즘이 끝나면, {{모노|prev[]}}의 자료구조는 원래 그래프의 일부 변이 제거된 부분 집합을 나타낼 것이다. 이 자료구조의 가장 중요한 특성은 알고리즘의 시작점이 여러 개였을 때, 새 그래프에서 그 꼭짓점에서 다른 꼭짓점으로 가는 모든 경로가 원래 그래프의 그 꼭짓점에서도 최단 경로라는 점과, 원본 그래프에서 그 길이를 가지는 모든 경로가 새로운 그래프에도 나타난다는 점이다. 실제로 주어진 두 꼭짓점 간의 최단 거리를 모두 찾기 위해서는 새로운 그래프에서 [[깊이 우선 탐색]] 같은 경로 찾기 알고리즘이 필요하다.
 
===우선순위 큐 사용===
 
[[우선순위 큐|최소 우선 큐]]는 다음의 세 기본 연산을 제공하는 추상 자료형이다: {{모노|add_with_priority()}}, {{모노|decrease_priority()}} 그리고 {{모노|extract_min()}}이다. 이전에 언급했듯이, 이런 자료구조를 사용하면 기본 큐를 사용하는 것 보다 계산 시간이 더 빨라질 수 있다. 특히, [[피보나치 힙]] {{harv|Fredman|Tarjan|1984}}이나 [[브로들 큐]]는 이 3가지 연산에 대해서 최적의 수행을 제공한다. 알고리즘이 약간 다르기 때문에 아래에 의사 코드로 나타냈다:
 
1 '''function''' Dijkstra(''Graph'', ''source''):
2 dist[''source''] ← 0 ''// 초기화''
3
4 create vertex set Q
5
6 '''for each''' vertex ''v'' in ''Graph'':
7 '''if''' ''v'' ≠ ''source''
8 dist[''v''] ← INFINITY ''// 소스에서 v까지의 아직 모르는 길이''
9 prev[''v''] ← UNDEFINED ''// v의 이전 노드''
10
11 ''Q''.add_with_priority(''v'', dist[''v''])
12
13
14 '''while''' ''Q'' is not empty: ''// 메인 루프''
15 ''u'' ← ''Q''.extract_min() ''// 최고의 꼭짓점을 제거하고 반환한다''
16 '''for each''' neighbor ''v'' of ''u'': ''// Q에 여전히 남아 있는 v에 대해서만''
17 ''alt'' ← dist[''u''] + length(''u'', ''v'')
18 '''if''' ''alt'' < dist[''v'']
19 dist[''v''] ← ''alt''
20 prev[''v''] ← ''u''
21 ''Q''.decrease_priority(''v'', ''alt'')
22
23 '''return''' dist, prev
 
초기화 단계에서 우선순위 큐에 모든 꼭짓점을 채우는 대신에, ''소스''만을 포함하도록 초기화 할 수 있다. 그러면, {{모노|'''if''' ''alt'' < dist[''v'']}} 블록에서 (<var>decrease_priority</var> 연산을 하는 대신에) 꼭짓점이 큐에 없다면 꼭짓점을 큐에 삽입해야 한다.<ref name="mehlhorn"/>{{rp|198}}
 
실제로 더 빠른 계산 시간을 얻기 위해서 다른 자료구조를 사용할 수 있다.<ref name=chen_07>{{서적 인용|first1=M.|last1=Chen|first2=R. A.|last2=Chowdhury|first3=V.|last3=Ramachandran|first4=D. L.|last4=Roche|first5=L.|last5=Tong|title=Priority Queues and Dijkstra’s Algorithm &mdash; UTCS Technical Report TR-07-54 &mdash; 12 October 2007|publisher=The University of Texas at Austin, Department of Computer Sciences|location=Austin, Texas|year=2007|url=http://www.cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf|ref=chen}}</ref>
 
== 정확성의 증명 ==
''데이크스트라 알고리즘의 증명은 방문한 꼭짓점의 숫자의 추론으로 이루어진다.''
 
''불변의 가설'': 방문한 꼭짓점 {{모노|v}}에 대해서, {{모노|dist[v]}}는 {{모노|source}}에서 {{모노|v}} 까지의 최단 거리로 간주하며, 미방문 꼭짓점 {{모노|u}}에 대해서는 {{모노|dist[u]}}를 방문한 꼭짓점 만을 통하는 {{모노|source}}에서 {{모노|u}}까지의 최단 거리로 간주한다. 이 가정은 경로가 존재할 때만 고려하지만, 존재하지 않으면 거리는 무한대로 설정된다. (참고 : 미방문 꼭짓점에 대해서는 {{모노|dist[u]}}를 실제 최단 길이로 간주하지 않는다)
 
기본적인 경우는 방문한 꼭짓점이 초기점인 {{모노|source}} 하나 밖에 없는 경우로, 이 가정은 [[자명성|자명하다]].
 
그렇지 않으면, 이 가정이 방문한 꼭짓점이 ''n-1''일 때 성립한다고 가정하자. 이 경우에, 모든 미방문 꼭짓점에서 {{모노|dist[u]}}가 가장 작은 {{모노|u}}에 대해서 {{모노|1=dist[u] = dist[v] + length[v,u]}}을 만족하는 변 {{모노|vu}}를 선택한다. {{모노|dist[u]}}는 {{모노|source}}에서 {{모노|u}}까지의 가장 짧은 거리로 볼 수 있다. 만약 그 경로보다 더 짧은 경로가 있고, 그 경로의 첫 번째 미방문 꼭짓점을 {{모노|w}}라고 한다면 처음의 가정인 {{모노|dist[w]}} > {{모노|dist[u]}}에 의해서 모순이 생긴다. 이와 비슷하게, {{모노|u}}로 가는 경로 중 미방문 꼭짓점을 지나지 않는 더 짧은 경로가 있고, 그 경로의 마지막 꼭짓점이 {{모노|w}}라고 한다면, {{모노|1=dist[u] = dist[w] + length[w,u]}}이여야 하기 때문에 여전히 모순이 생긴다.
 
 
{{모노|u}}를 처리하고 나서도 각각의 미방문 꼭짓점 {{모노|w}}에 대해서, {{모노|dist[w]}}는 여전히 방문한 꼭짓점만을 통해서 {{모노|source}}에서 {{모노|w}}로까지의 최단 거리이다. 그 이유는 {{모노|u}}를 통과하지 않는 경로 중 더 짧은 경로가 있다고 한다면 이미 찾았었을 것이며, {{모노|u}}를 통하는 경로가 더 짧다면 {{모노|u}}를 처리할 때 갱신되었을 것이기 때문이다.
 
== 실행 시간 ==
<math>m</math>개의 변과 <math>n</math>개의 [[꼭짓점]]을 가진 [[그래프]]에 대해 [[대문자 O 표기법]]으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다.
 
{{mvar|E}}를 변으로 가지고 {{mvar|V}}를 꼭짓점으로 가지는 그래프에서 데이크스트라 알고리즘의 실행 시간의 상한은 [[대문자 O 표기법]]을 사용해서 변의 갯수 <math>|E|</math>와 꼭짓점의 갯수 <math>|V|</math>의 함수로 나타낼 수 있다. 상한을 어떻게 정하는지는 꼭짓점 집합 {{mvar|Q}}을 수행하는 방법에 의존한다. 다음에서, 어떤 그래프든지 <math>|E| = O(|V|^2)</math>이기 때문에 상한을 단순화 할 수 있지만, 이 단순화는 <math>|E|</math>에 대한 다른 상한이 있을 수 있다는 점을 간과한다.
가장 간단한 구현으로, ''Q''의 집합을 [[연결 리스트]]나 [[배열]] 구조로 구현하고 Extract-Min(Q) 함수를 단순한 [[선형 탐색]]으로 구현했을 때 실행 시간은 <math>O(n^2)</math> 시간이 된다.
 
꼭짓점 집합 {{mvar|Q}}의 어떤 수행에서든지 수행 시간은 다음에 포함되어있다:
만약 희소 그래프(sparse graph), 즉 <math>n^2</math>보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, [[인접 리스트]]와 바이너리 [[힙 (자료 구조)|힙]] 또는 [[피보나치 힙]]으로 구현한 [[우선순위 큐]]를 이용해 데이크스트라 알고리즘을 더 효율적으로 구현할 수 있다. [[이진 힙]]을 이용하면 실행 시간은 <math>O((m+n)\log n)</math> 시간이 되고, [[피보나치 힙]]을 통해 <math>O(m + n \log n)</math> 시간까지 개선할 수 있다.
:<math>O(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em})</math>
이 때 <math>T_\mathrm{dk}</math>와 <math>T_\mathrm{em}</math>은 각각{{mvar|Q}}에서 ''decrease-key''와 ''extract-minimum'' 연산의 복잡성이다. 가장 간단한 데이크스트라 알고리즘은 꼭짓점 집합 {{mvar|Q}}를 일반적인 연결 리스트나 배열로 저장하고, extract-minimum은 단순히 {{mvar|Q}}에 있는 모든 꼭짓점의 선형 탐색 이다. 따라서 이 경우에 실행 시간은 <math>O(|E| + |V|^2) = O(|V|^2)</math>이다.
 
변이 <math>|V|^2</math>보다 한참 적은 [[희소 그래프]]에 대해서는, 데이크스트라 알고리즘은 그래프를 [[인접 리스트]]의 형태로 저장하고 최소 추출을 효율적으로 하기 위해서 [[우선순위 큐]]로 [[자가 균형 이진 탐색 트리]], [[이진 힙]], [[페어링 힙]], 또는 [[피보나치 힙]]을 사용해서 효율적으로 수행할 수 있다. decrease-key 단계를 이진 힙으로 효율적으로 수행하기 위해서는 각각의 꼭짓점에서 힙의 위치로 연결하는 보조 자료 구조를 사용하고 우선순위 큐 {{mvar|Q}}가 바뀔 때 마다 갱신할 필요가 있다. 자가 균형 이진 탐색 트리나 이진 힙에서 데이크스트라 알고리즘은 최악의 경우에 다음의 시간이 필요하다(<math>\log</math>는 이진 로그 <math>\log_2</math>를 의미한다):
:<math>\Theta((|E| + |V|) \log |V|)</math>
연결 그래프에서는 이 시간 상한을 <math>\Theta( | E | \log | V | )</math>로 단순화 할 수 있다. [[피보나치]] 힙은 이 시간을 다음과 같이 개선시킬 수 있다:
:<math>O(|E| + |V| \log|V|)</math>.
 
이진 힙을 사용할 때, [[최선, 최악, 그리고 평균의 경우|평균]] 시간복잡도는 최악의 경우 보다 더 낮다: 변의 비용이 일반적인 [[확률 분포]]와 무관하다고 가정하면, ''decrease-key'' 연산의 기대 연산 횟수의 상한은 <math>O(|V| \log (|E|/|V|))</math>이므로, 총 수행 시간은 다음과 같아진다:{{r|mehlhorn}}{{rp|199–200}}
:<math>O\left(|E| + |V| \log \frac{|E|}{|V|} \log |V|\right)</math>.
 
게다가, 그래프에 있는 모든 꼭짓점을 삽입하지 않으면 알고리즘을 무한 그래프나 메모리로 표현하기에는 너무 큰 그래프에서 시작점에서 도착점까지의 최단 경로를 찾도록 확장할 수 있다. 그 결과로 나타나는 알고리즘은 인공지능 분야에서 ''균일 비용 탐색'' (UCS)이라고 불리고{{r|felner}}<ref name="aima">{{Cite AIMA|3|pages=75, 81}}</ref><ref>또는 종종 ''최소 비용 우선 탐색''이라고도 불린다: {{저널 인용|last=Nau |first=Dana S. |title=Expert computer systems |journal=Computer |publisher=IEEE |volume=16 |issue=2 |year=1983 |pages=63–85 |url=https://www.cs.umd.edu/~nau/papers/nau1983expert.pdf |doi=10.1109/mc.1983.1654302}}</ref> 다음의 의사 코드로 나타낼 수 있다
'''procedure''' ''UniformCostSearch''(Graph, start, goal)
node ← start
cost ← 0
frontier ← priority queue containing node only
explored ← empty set
'''do'''
'''if''' frontier is empty
'''return''' failure
node ← frontier.pop()
'''if''' node is goal
'''return''' solution
'''for each''' of node's neighbors n
'''if''' n is not in explored
frontier.add(n)
explored.add(n)
 
이 알고리즘의 복잡성은 매우 큰 그래프에서 다른 방법으로 표현할 수 있다: {{math|''C''<sup>*</sup>}}가 시작점에서 "도착" 예측을 만족하는 어떤 점으로 가는 최단 경로의 길이라고 하고, 각각의 변이 적어도 {{mvar|ε}}의 비용이 들며, 꼭짓점의 인접 꼭짓점의 갯수가 최대 {{mvar|b}}라고 한다면, 알고리즘의 최악의 경우와 공간복잡도는 둘 다 {{math|''O''(''b''<sup>1+⌊''C''<sup>*</sup> {{frac}} ''ε''⌋</sup>)}}이다.{{r|aima}}
 
단일 도착점의 경우의 데이크스트라 알고리즘을 더 최적화 한 것에는 [[양방향 탐색|양방향]] 변형이 있고, [[A* 알고리즘]] 같은 목적 지향 변형이 있으며({{slink||관련 문제와 알고리즘}} 참고), 어떤 꼭짓점이 최단 경로의 일부를 이룰 것 같은지를 결정하기 위한 그래프 가지치기가 있으며 (도달 기반 라우팅), {{mvar|s}}와 {{mvar|t}}를 각각 "고속도로"를 이용한 전이 꼭짓점 간의 최단 경로 계산에 의한 "전이 꼭짓점"으로 연결시키기 위해서 {{math|''s''–''t''}} 라우팅을 감소시키는 입력된 그래프의 계급 분해를 사용할 수 있다.<ref name="speedup">{{콘퍼런스 인용|last1=Wagner |first1=Dorothea |first2=Thomas |last2=Willhalm |title=Speed-up techniques for shortest-path computations |conference=STACS |pages=23–36 |year=2007}}</ref>
이러 기술을 결합하는 것은 특정 문제에서 실제 최적의 수행에 필요할 수 있다.<ref>{{저널 인용|last1=Bauer |first1=Reinhard |first2=Daniel |last2=Delling |first3=Peter |last3=Sanders |first4=Dennis |last4=Schieferdecker |first5=Dominik |last5=Schultes |first6=Dorothea |last6=Wagner |title=Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm |journal=J. Experimental Algorithmics |volume=15 |year=2010}}</ref>
 
<span id="세분화된 변형">
 
===세분화된 변형===
변의 비용<!--arc weights-->이 작은 정수일 때(''C'' 보다 작을 때), 데이크스트라 알고리즘의 속도를 높이기 위해서 [[단조 우선순위 큐]]를 쓸 수 있다. 이 종류의 첫 번째 알고리즘은 '''Dial's algorithm'''으로, [[버켓 큐]]를 사용해서 수행 시간이 <math>O(|E|+\operatorname{diam}(G))</math>로, 정수 가중치를 갖는 그래프의 가중 [[거리 (그래프 이론)|지름]]에 의존한다{{harv|Dial|1969}}. [[판엠더 보아스 트리]]<!--Van Emde Boas tree-->를 우선순위 큐로 사용하면 복잡성은 <math>O(|E|\log\log C)</math>가 된다{{harv|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}. 새로운 [[기수 힙]]과 잘 알려진 피보나치 힙의 결합에 기반한 수행은 <math>O(|E|+|V|\sqrt{\log C})</math>의 시간이 소요된다{{harv|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}. 마지막으로, 여기에서 언급한 특수한 경우에 대한 최적의 알고리즘은 다음과 같다. {{harv|Thorup|2000}}의 알고리즘은 <math>O(|E|\log\log|V|)</math>의 시간이 소요되고 {{harv|Raman|1997}}의 알고리즘은 <math>O(|E| + |V|\min\{(\log|V|)^{1/3+\epsilon}, (\log C)^{1/4+\epsilon}\})</math>의 시간이 소요된다.
 
또한 [[유향 비순환 그래프]]에서는 꼭짓점의 [[위상정렬|위상적 순서]]를 처리하고 각각의 꼭짓점까지의 길이를 들어오는 변을 통한 경로 중 최소 거리로 설정하면 주어진 시작점에서 선형 시간 <math>O(|E|+|V|)</math>만에 최단 경로를 찾을 수 있다.<ref>http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html</ref><ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=655}}</ref>
 
가중치가 정수인 무향 연결 그래프의 경우의 데이크스트라 알고리즘은 {{harv|Thorup|1999}}에 의해 완전히 선형 복잡도 <math>O(|E|)</math>를 가진다.
</span>
 
== 관련 문제와 알고리즘 ==
 
데이크스트라의 원 알고리즘의 기능성은 변형의 다양성을 통해 확장할 수 있다. 예를 들면, 종종 수학적으로 덜 최적인 해법을 나타내는 것이 바람직할 때가 있다. 최적 이하의 해법의 순위표를 얻기 위해서는 먼저 최적 해법을 계산해야 한다. 최적 해법의 한 변을 그래프에서 제거하고, 이 새로운 그래프에서 최적 해법을 계산한다. 원래 해법의 각각의 변을 차례로 제거하고 새로운 최단 경로를 계산한다. 그러면 두 번째 해법을 순위매기고 첫 번째 최적 해법의 다음에 표시한다.
 
데이크스트라 알고리즘은 종종 [[링크 상태 라우팅 프로토콜]]<!--link-state routing protocol-->의 원리에 의해 작동하며, [[OSPF]]와 [[IS-IS]]가 그중 가장 일반적인 것이다.
 
데이크스트라 알고리즘과는 달리, [[벨먼-포드 알고리즘]]은 소스 꼭짓점 ''s''에서 도달할 수 있는 [[음수 사이클]]이 없으면 음수 가중치가 있을 때에도 사용할 수 있다. 이런 사이클이 존재하면, 이 사이클에 들어가서 한 바퀴를 돌 때 마다 전체 비용이 감소하기 때문에 최단 경로가 없다. 데이크스트라 알고리즘에 (음수 변을 제거하고 음수 사이클을 감지하기 위해)벨먼-포드 알고리즘을 결합해서 음수 가중치를 다룰 수 있으며, 이런 알고리즘은 [[존슨 알고리즘]]이라고 불린다.
 
[[A* 알고리즘]]은 데이크스트라 알고리즘을 일반화 한 것으로, 목적지까지의 "거리"의 하한에 관한 정보를 얻을 수 있을 때 탐색해야 할 부분 그래프의 크기를 줄일 수 있다. 이 접근은 [[선형 계획법]]의 관점에서 볼 수 있다: there is a natural [[최단 경로 문제#선형 계획법 공식|최단 경로의 계산에서 선형 계획법]]이 있고, 그 [[쌍대성 (최적화)|쌍대 선형 계획법]]의 해법이 실행 가능하다는 것은 [[일관 휴리스틱]]을 형성한다는 것이다(대략적으로 말하면, 서명 관례가 문헌마다 다르기 때문이다). 이 실행 가능한 쌍대 / 일관 휴리스틱은 음이 아닌 [[감소 비용]]을 정의하고 A*은 본질저그로 이 감소 비용을 가지고 데이크스트라 알고리즘을 돌리는 것이다. 쌍대 선형 계획법이 약한 [[허용적 휴리스틱|허용성]] 조건을 만족하면, A*는 벨먼-포드 알고리즘에 더 비슷하다.
 
데이크스트라 알고리즘의 기초가 되는 과정은 [[프림 알고리즘]]에서 사용되는 [[탐욕 알고리즘|탐욕]] 과정과 유사하다. 프림 알고리즘의 목적은 그래프에 있는 모든 꼭짓점을 연결하는 [[최소 신장 트리]]를 찾는 것이나, 데이크스트라 알고리즘은 꼭짓점 두 개 만을 고려하는 것이다. 프림 알고리즘은 시작 꼭짓점의 전체 가중치로 평가하지 않고 각각의 가중치만을 평가한다.
 
[[너비 우선 탐색]]은 데이크스트라 알고리즘을 비가중 그래프에서, 우선순위 큐를 선입선출(FIFO) 큐로 만든 특수한 경우로 볼 수 있다.
 
[[빠른 행진 방법]]<!--fast marching method-->는 삼각형 메쉬의 지오데식 거리를 계산하는 데이크스트라 알고리즘의 연속적인 버전으로 볼 수 있다.
 
=== 동적 계획법의 관점 ===
 
[[동적 계획법]]의 관점에서 보면, 데이크스트라 알고리즘은 '''도달''' 방법<!--'''Reaching''' method-->에서 생겨난 최단 경로 문제에 대한 동적 계획법 함수적 방정식을 푸는 연속적 근사 계획법이다.<ref name=sniedovich_06>{{저널 인용| last = Sniedovich | first = M. | title = Dijkstra’s algorithm revisited: the dynamic programming connexion | journal = Journal of Control and Cybernetics | volume = 35 | issue = 3 | pages = 599–620 | year = 2006 | url = http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf | format = [[PDF]]}} [http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html 인터랙티브 계산 모듈이 있는 논문의 온라인 버전.]</ref><ref name=denardo_03>{{서적 인용| last = Denardo | first = E.V. | title = Dynamic Programming: Models and Applications | publisher = [[도버 출판사|Dover Publications]] | location = Mineola, NY | year = 2003 | isbn = 978-0-486-42810-9}}</ref><ref name=sniedovich_10>{{서적 인용| last = Sniedovich | first = M. | title = Dynamic Programming: Foundations and Principles | publisher = [[테일러 앤 프랜시스|Francis & Taylor]] | year = 2010 | isbn = 978-0-8247-4099-3 }}</ref>
 
사실, 알고리즘의 바탕이 되는 논리에 대한 데이크스트라의 설명<ref>{{harvnb|Dijkstra|1959|p=270}}</ref>
{{quote|
'''문제 2.''' 주어진 두 개의 꼭짓점 <math>P</math>와 <math>Q</math>사이의 최소 거리를 가지는 경로를 찾아라.
 
<math>R</math>이 <math>P</math>에서 <math>Q</math>로 가는 최단 경로에 있는 꼭짓점이라면, 이 경로는 마찬가지로 <math>P</math>에서 <math>R</math>까지 가는 최단 경로라는 사실을 이용한다.
<!--'''Problem 2.''' Find the path of minimum total length between two given nodes <math>P</math> and <math>Q</math>.
 
We use the fact that, if <math>R</math> is a node on the minimal path from <math>P</math> to <math>Q</math>, knowledge of the latter implies the knowledge of the minimal path from <math>P</math> to <math>R</math>.-->
}}
 
은 [[리처드 벨먼|벨먼]]의 유명한 [[최적성의 원리]]를 최단 경로 문제의 맥락에서 해석한 것이다.
== 관련된 문제와 알고리즘 ==
인터넷 [[라우팅]]에서 사용되는 [[최단 경로 우선 프로토콜]]은 데이크스트라 알고리즘이 실제 현장에서 사용되는 좋은 사례이다.
 
== 같이 보기 ==
그래프의 가중치가 음수가 아니라고 가정하는 데이크스트라 알고리즘과는 달리, [[벨먼-포드 알고리즘]]은 음수 가중치를 갖는 그래프에 대해서도 정확하게 동작한다. (단, 그래프에 음수 값을 갖는 순환 경로가 존재하지 않을 때)
* [[A* 알고리즘]]
* [[벨먼-포드 알고리즘]]
* [[유클리드 최단 경로]]
* [[플러드 필]]
* [[플로이드-워셜 알고리즘]]
* [[존슨 일고리즘]]
* [[최장 경로 문제]]
 
==참조==
목적지까지의 '거리'를 추정할 수 있는 방법이 있을 때, 데이크스트라 알고리즘의 변형인 [[A* 알고리즘]]은 탐색해야 할 그래프의 크기를 줄이는 방법으로 더 빠르게 경로를 찾을 수 있다.
{{reflist}}
 
== 참고 문헌 ==
* {{서적 인용| author1-link = Thomas H. Cormen | first1 = Thomas H. | last1 = Cormen | author2-link = Charles E. Leiserson | first2 = Charles E. | last2 = Leiserson | author3-link = Ronald L. Rivest | first3 = Ronald L. | last3 = Rivest | author4-link = Clifford Stein | first4 = Clifford | last4 = Stein | title = [[Introduction to Algorithms]] | edition = Second | publisher = [[MIT Press]] and [[McGraw–Hill]] | year = 2001 | isbn = 0-262-03293-7 | chapter = Section 24.3: Dijkstra's algorithm | pages = 595–601 | ref = harv}}
* 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.&nbsp;595–601.
| last = Dial | first = Robert B.
| doi = 10.1145/363269.363610
| issue = 11
| journal = [[Communications of the ACM]]
| pages = 632–633
| title = Algorithm 360: Shortest-path forest with topological ordering [H]
| volume = 12
| year = 1969
| ref = harv}}
* {{콘퍼런스 인용|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|conference=25th Annual Symposium on Foundations of Computer Science|year=1984|publisher=[[IEEE]]|pages=338&ndash;346|ref=harv|doi=10.1109/SFCS.1984.715934}}
* {{저널 인용|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=Journal of the Association for Computing Machinery|volume=34|year=1987|pages=596&ndash;615|url=http://portal.acm.org/citation.cfm?id=28874|ref=harv|doi=10.1145/28869.28874|issue=3}}
* {{저널 인용| first1 = F. Benjamin | last1 = Zhan | first2 = Charles E. | last2 = Noon |date=February 1998 | title = Shortest Path Algorithms: An Evaluation Using Real Road Networks | journal = [[Transportation Science]] | volume = 32 | issue = 1 | pages = 65–73 | doi = 10.1287/trsc.32.1.65}}
* {{서적 인용|first1=M.|last1=Leyzorek|first2=R. S.|last2=Gray|first3=A. A.|last3=Johnson|first4=W. C.|last4=Ladew|first5=S. R.|last5=Meaker, Jr.|first6=R. M.|last6=Petry|first7=R. N.|last7=Seitz|title=Investigation of Model Techniques &mdash; First Annual Report &mdash; 6 June 1956 &mdash; 1 July 1957 &mdash; A Study of Model Techniques for Communication Systems|publisher=Case Institute of Technology|location=Cleveland, Ohio|year=1957|ref=harv}}
* {{저널 인용|first1=D.E.|last1=Knuth|title=A Generalization of Dijkstra's Algorithm|journal=[[Information Processing Letters]]|volume=6|number=1|pages=1–5|year=1977|authorlink1=Donald Knuth|doi=10.1016/0020-0190(77)90002-3}}
* {{저널 인용|first1=Ravindra K.|last1=Ahuja|first2=Kurt|last2=Mehlhorn|first3=James B.|last3=Orlin|first4=Robert E.|last4=Tarjan|title=Faster Algorithms for the Shortest Path Problem|journal=Journal of the ACM|volume=37|number=2|pages=213–223| date=April 1990 |doi=10.1145/77600.77615|ref=harv}}
* {{저널 인용|first1=Rajeev|last1=Raman|title=Recent results on the single-source shortest paths problem|journal=SIGACT News|volume=28|issue=2|pages=81–87|year=1997|ref=harv|doi=10.1145/261342.261352}}
* {{저널 인용|first1=Mikkel|last1=Thorup|title=On RAM priority Queues|journal=SIAM Journal on Computing|volume=30|issue=1|pages=86–109|year=2000|doi=10.1137/S0097539795288246|ref=harv}}
* {{저널 인용|first1=Mikkel|last1=Thorup|title=Undirected single-source shortest paths with positive integer weights in linear time|journal=journal of the ACM|volume=46|issue=3|pages=362–394|year=1999|doi=10.1145/316542.316548|ref=harv|url=http://www.diku.dk/users/mthorup/PAPERS/sssp.ps.gz}}
 
== 외부 링크 ==
{{위키공용분류|Dijkstra's algorithm}}
* [http://en.wikisource.org/wiki/Dijkstra%27s_algorithm 여러 가지 구현]
* [http://purl.umn.edu/107247 Oral history interview with Edsger W. Dijkstra], [[Charles Babbage Institute]] University of Minnesota, Minneapolis.
* [http://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html Implementation of Dijkstra's algorithm using TDD], [[Robert Cecil Martin]], The Clean Code Blog
* [http://www.gilles-bertrand.com/2014/03/disjkstra-algorithm-description-shortest-path-pseudo-code-data-structure-example-image.html Graphical explanation of Dijkstra's algorithm step-by-step on an example], [[Gilles Bertrand]], A step by step graphical explanation of Dijkstra's algorithm operations
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html 데이크스트라 알고리즘의 애니메이션]
* [http://www.boost.org/libs/graph/doc/index.html Boost 그래프 라이브러리(BGL)]
* [http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm 대화형인터랙티브 구현수행]
 
[[분류:그래프 알고리즘]]
[[분류:탐색 알고리즘]]
[[분류:라우팅 알고리즘]]
[[분류:조합최적화]]
[[분류:사람의사코드가 이름을있는 딴 낱말문서]]