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

잔글
잔글 (ChongDae님이 다익스트라 알고리즘 문서를 데이크스트라 알고리즘 문서로 이동하면서 넘겨주기를 덮어썼습니다)
잔글 (+분류:에츠허르 데이크스트라; 예쁘게 바꿈)
== 의사 코드 ==
 
다음 알고리즘에서, 코드 {{모노|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|섬네일|유클리드 거리에 기반한 데이크스트라 알고리즘의 시연이다. 빨간색 선은 최단 경로이다. 다시 말해, ''u''와 [''u'']를 연결하는 선이다. 파란 선은 변 경감이 이루어지는 위치를 나타낸다. 즉, ''v''와 ''Q''에 있는 꼭짓점 ''u''를 연결하는 선으로, 소스에서 ''v''까지 가는 더 짧은 경로를 나타낸다.]]
 
더 일반적인 문제는 {{모노|<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가지 연산에 대해서 최적의 수행을 제공한다. 알고리즘이 약간 다르기 때문에 아래에 의사 코드로 나타냈다:
초기화 단계에서 우선순위 큐에 모든 꼭짓점을 채우는 대신에, ''소스''만을 포함하도록 초기화 할 수 있다. 그러면, {{모노|'''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>
 
== 정확성의 증명 ==
<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>의 시간이 소요된다.
 
* [[최장 경로 문제]]
 
== 참조 ==
{{각주}}
 
| 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;346338–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;615596–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}}
== 외부 링크 ==
{{위키공용분류|Dijkstra's 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
[[분류:조합최적화]]
[[분류:의사코드가 있는 문서]]
[[분류:에츠허르 데이크스트라]]

편집

1,174,591