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

[[컴퓨터 과학]]에서, 다익'''스트라데이크스트라 알고리즘'''({{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}} 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 [[최단 경로 트리]]를 만드는 것이다.

그래프에서 주어진 소스 꼭짓점에 대해서, 다익스트라데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다.<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)에서 주로 사용된다. 또한 다익스트라데이크스트라 알고리즘은 [[존슨 알고리즘]] 같은 알고리즘의 [[서브루틴]]으로 채택되었다.

다익스트라의데이크스트라의 원래 알고리즘은 [[우선순위 큐|최소 우선 큐]]를 사용하지 않았기 때문에 [[시간 복잡도]]가 <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||세분화된 변형}}으로 개선할 수 있다.

어떤 분야, 특히 [[인공 지능]] 분야에서, 다익스트라데이크스트라 알고리즘이나 그 변형은 '''균일 비용 탐색'''으로 알려져 있으며 [[최상 우선 탐색]]의 일반적인 아이디어의 예시로 공식화 되어있다.<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>

다익스트라는데이크스트라는 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-07-18|deadurl=예no|df=dmy-all|확인날짜=2018-06-21}}</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|섬네일|[[로봇공학|로봇]] [[모션 계획]] 문제에서 다익스트라데이크스트라 알고리즘이 시작점(좌측 하단, 빨간색)에서 도착점(우측 상단, 초록색)까지의 경로를 찾는 도해. 빈 꼭짓점은 "시험" 집합("미방문" 꼭짓점들의 집합)을 나타낸다. 채워진 꼭짓점은 방문한 꼭짓점으로, 색은 거리를 나타낸다: 초록색이 될 수록 더 가깝다는 의미이다. 다른 방향으로 있는 꼭짓점들은 균일하게 탐색되며, 다익스트라데이크스트라 알고리즘이 [[균일 휴리스틱|휴리스틱]]을 0과 같게 사용하기 때문에 원형 [[파면]]으로 적거나 많게 나타난다.]]

시작할 꼭짓점은 '''초기점'''으로, '''꼭짓점 ''Y''의 거리'''를 '''초기점'''에서 ''Y''까지의 거리로 정의한다. 다익스트라데이크스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 '''간선 완화'''('''edge relaxation''')이라고 한다.

도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 하자. 다익스트라데이크스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장 짧은 거리를 찾는다.

다익스트라데이크스트라 알고리즘에서는 우선 모든 교차점에 ''무한대''를 적어놓는다. 이 표시는 실제 거리가 무한대라는 뜻이 아니라 교차로에 가보지 않았다는 것을 의미한다. 변형된 다익스트라데이크스트라 알고리즘에서는 ''표시되지 않음''을 써놓기도 한다.

이 알고리즘은 목적지를 향해서 조사하지 않고, 목적지까지의 최단거리보다 짧은 교차로들을 모두 고려하기 때문에 최단 거리를 찾을 수 있게 된다. 하지만 모든 교차로를 고려한다는 특징으로 인해 다익스트라데이크스트라 알고리즘은 특정한 지도에서 상대적으로 느리게 작동할 수 있다.

[[파일:DijkstraDemo.gif|섬네일|유클리드 거리에 기반한 다익스트라데이크스트라 알고리즘의 시연이다. 빨간색 선은 최단 경로이다. 다시 말해, ''u''와 [''u'']를 연결하는 선이다. 파란 선은 변 경감이 이루어지는 위치를 나타낸다. 즉, ''v''와 ''Q''에 있는 꼭짓점 ''u''를 연결하는 선으로, 소스에서 ''v''까지 가는 더 짧은 경로를 나타낸다.]]

다익스트라데이크스트라 알고리즘은 방문한 노드에 쓰여진 숫자를 이용하여 귀납적으로 증명할 수 있다.

간선 {{mvar|E}}와 꼭짓점{{mvar|V}}를 가지는 그래프에서 다익스트라데이크스트라 알고리즘의 실행 시간의 상한은 [[대문자 O 표기법]]을 사용해서 변의 개수 <math>|E|</math>와 꼭짓점의 개수 <math>|V|</math>의 함수로 나타낼 수 있다. 상한을 어떻게 정하는지는 꼭짓점 집합 {{mvar|Q}}을 수행하는 방법에 의존한다. 다음에서, 어떤 그래프든지 <math>|E| = O(|V|^2)</math>이기 때문에 상한을 단순화 할 수 있지만, 이 단순화는 <math>|E|</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>를 의미한다):

단일 도착점의 경우의 다익스트라데이크스트라 알고리즘을 더 최적화 한 것에는 [[양방향 탐색|양방향]] 변형이 있고, [[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>

변의 비용<!--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>의 시간이 소요된다.

가중치가 정수인 무향 연결 그래프의 경우의 다익스트라데이크스트라 알고리즘은 {{harv|Thorup|1999}}에 의해 완전히 선형 복잡도 <math>O(|E|)</math>를 가진다.

다익스트라의데이크스트라의 원 알고리즘의 기능성은 변형의 다양성을 통해 확장할 수 있다. 예를 들면, 종종 수학적으로 덜 최적인 해법을 나타내는 것이 바람직할 때가 있다. 최적 이하의 해법의 순위표를 얻기 위해서는 먼저 최적 해법을 계산해야 한다. 최적 해법의 한 변을 그래프에서 제거하고, 이 새로운 그래프에서 최적 해법을 계산한다. 원래 해법의 각각의 변을 차례로 제거하고 새로운 최단 경로를 계산한다. 그러면 두 번째 해법을 순위매기고 첫 번째 최적 해법의 다음에 표시한다.

다익스트라데이크스트라 알고리즘은 종종 [[링크 상태 라우팅 프로토콜]]<!--link-state routing protocol-->의 원리에 의해 작동하며, [[OSPF]]와 [[IS-IS]]가 그중 가장 일반적인 것이다.

다익스트라데이크스트라 알고리즘과는 달리, [[벨먼-포드 알고리즘]]은 소스 꼭짓점 ''s''에서 도달할 수 있는 [[음수 사이클]]이 없으면 음수 가중치가 있을 때에도 사용할 수 있다. 이런 사이클이 존재하면, 이 사이클에 들어가서 한 바퀴를 돌 때 마다 전체 비용이 감소하기 때문에 최단 경로가 없다. 다익스트라데이크스트라 알고리즘에 (음수 변을 제거하고 음수 사이클을 감지하기 위해)벨먼-포드 알고리즘을 결합해서 음수 가중치를 다룰 수 있으며, 이런 알고리즘은 [[존슨 알고리즘]]이라고 불린다.

[[A* 알고리즘]]은 다익스트라데이크스트라 알고리즘을 일반화 한 것으로, 목적지까지의 "거리"의 하한에 관한 정보를 얻을 수 있을 때 탐색해야 할 부분 그래프의 크기를 줄일 수 있다. 이 접근은 [[선형 계획법]]의 관점에서 볼 수 있다: [[최단 경로 문제#선형 계획법 공식|최단 경로의 계산에서 선형 계획법]]이 있고, 그 [[쌍대성 (최적화)|쌍대 선형 계획법]]의 해법이 실행 가능하다는 것은 [[일관 휴리스틱]]을 형성한다는 것이다(대략적으로 말하면, 서명 관례가 문헌마다 다르기 때문이다). 이 실행 가능한 쌍대 / 일관 휴리스틱은 음이 아닌 [[감소 비용]]을 정의하고 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>

* [[존슨 일고리즘|존슨 알고리즘]]

* {{서적 인용| 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}}

* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html 다익스트라데이크스트라 알고리즘의 애니메이션]