은 벨먼의 유명한 최적성의 원리를 최단 경로 문제의 맥락에서 해석한 것이다. 같이 보기 [ 편집 ] A * 알고리즘 벨먼 - 포드 알고리즘 유클리드 최단 경로 플러드 필 플로이드 - 워셜 알고리즘 존슨 일고리즘 최장 경로 문제 참조 [ 편집 ] ↑ Richards, Hamilton. " Edsger Wybe Dijkstra ". 《 A. M. Turing Award 》. Association for Computing Machinery. 2017년 10월 16일에 확인함. 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 ↑ 가 나 다 Frana, Phil ( August 2010 ). " An Interview with Edsger W. Dijkstra ". 《 Communications of the ACM 》 53 ( 8 ) : 41 - 47. doi : 10. 1145 / 1787234. 1787249. ↑ 가 나
가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS - IS ( Intermediate System to Intermediate System ) 와 OSPF ( Open Shortest Path First ) 에서 주로 사용된다. 또한 데이크스트라 알고리즘은 존슨 알고리즘 같은 알고리즘의 서브루틴으로 채택되었다. 데이크스트라의 원래 알고리즘은 최소 우선 큐를 사용하지 않았기 때문에 시간 복잡도가 O ( | V | 2 ) { displaystyle O ( | V | ^ { 2 } ) } ( | V | { displaystyle | V | } 는 꼭짓점의 개수이다 ) 이다. 이 알고리즘의 개념은 Leyzorek 외. 1957에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간복잡도는 Fredman & Tarjan 1984 때문에 O ( | E | | V | log | V | ) { displaystyle O ( | E | | V
Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford ( 2001 ). 〈 Section 24. 3 : Dijkstra's algorithm 〉. 《 Introduction to Algorithms 》 Seco판. MIT Press and McGraw - Hill. 595 - 601쪽. ISBN 0 - 262 - 03293 - 7. Dial, Robert B. ( 1969 ). " Algorithm 360 : Shortest - path forest with topological ordering [ H ] ". 《 Communications of the ACM 》 12 ( 11 ) : 632 - 633. doi : 10. 1145 / 363269. 363610. Fredman, Michael Lawrence ; Tarjan, Robert E. ( 1984 ). 《 Fibonacci heaps and their uses in improved network optimization algorithms 》. 25th Annual Symposium on Foundations of Computer Science. IEEE. 338 - 346쪽. doi : 10. 1109 / SFCS. 1984. 715934. Fredman, Michael Lawrence ; Tarjan, Robert E
##le B }, 이웃 교차로에 쓰여 있는 거리를 C { displaystyle C } 라고 할 때, A B < C { displaystyle AB < C } 이면 이웃 교차로에 최단 거리는 A B { displaystyle AB } 이며 이 값은 T { displaystyle T } 로부터 계산되었다라고 쓴다. 이 과정을 완화라고 한다. 현재 위치에서 연결된 모든 이웃 교차로에 대해 완화가 끝나면 현재 위치에 방문함이라고 적고 현재 위치에서 가장 가까운, 방문하지 않은 교차로로 이동한다. 방문표시가 된 교차로에는 항상 최단거리가 적혀있을 것이다. 만약 방문하지 않은 이웃 교차로가 없는 경우에는 현재 위치의 거리가 계산된 교차로로 돌아가서 가까운 방문하지 않은 교차로로 이동한다. 현재 위치가 목적지라면 탐색을 종료한 뒤 최단 거리를 바탕으로 최단 경로를 찾는다. 출발지를 제외한 모든 교차로에는 자신이 계산되어온 교차로가 쓰여 있을 것이다. 이 교차로를 부모 노드라고 한다. 목적지에서 부모 노드를 계속 따라가면 최단경로를 따라서 출발지에 도착하게 된다. 이 알고리즘은 목적지를 향해서 조사하지 않고, 목적지까지의 최단거리보다 짧은 교차로들을 모두 고려하기 때문에 최단 거리를 찾을 수 있게 된다.
T - { mathrm { dk } } } 와 T e m { displaystyle T - { mathrm { em } } } 은 각각Q에서 decrease - key와 extract - minimum 연산의 복잡성이다. 가장 간단한 데이크스트라 알고리즘은 꼭짓점 집합 Q를 일반적인 연결 리스트나 배열로 저장하고, extract - minimum은 단순히 Q에 있는 모든 꼭짓점의 선형 탐색 이다. 따라서 이 경우에 실행 시간은 O ( | E | | V | 2 ) = O ( | V | 2 ) { displaystyle O ( | E | | V | ^ { 2 } ) = O ( | V | ^ { 2 } ) } 이다. 변이 | V | 2 { displaystyle | V | ^ { 2 } } 보다 한참 적은 희소 그래프에 대해서는, 데이크스트라 알고리즘은 그래프를 인접 리스트의 형태로 저장하고 최소 추출을 효율적으로 하기 위해서 우선순위 큐로 자가 균형 이진 탐색 트리, 이진 힙, 페어링 힙, 또는 피보나치 힙을 사용해서 효율적으로 수행할 수 있다. decrease - key 단계를 이진 힙으로 효율적으로 수행하기 위해서는 각각의 꼭짓점에서 힙의 위치로 연결하는 보조 자료 구조를 사용하고 우선순위 큐 Q가 바뀔
지도라는 용어를 사용했지만, 공식적인 용어는 각각 꼭짓점, 변 그리고 그래프이다. 도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 하자. 데이크스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장 짧은 거리를 찾는다. 데이크스트라 알고리즘에서는 우선 모든 교차점에 무한대를 적어놓는다. 이 표시는 실제 거리가 무한대라는 뜻이 아니라 교차로에 가보지 않았다는 것을 의미한다. 변형된 데이크스트라 알고리즘에서는 표시되지 않음을 써놓기도 한다. 다음으로는 모든 교차점을 표시할 때까지 반복한다. 우선 현재 위치를 정하고 시작점으로부터의 거리를 쓴다. 시작할 때의 현재 위치는 시작점이다. 그리고 시작점으로부터의 거리는 당연히 0이다. 그 다음 현재 위치와 연결되어있는 교차로들의 거리를 갱신한다. 현재 위치에는 시작점으로부터 가장 짧은 거리가 쓰여 있다. 현재 위치 T { displaystyle T } 에 쓰여 있는 거리를 A { displaystyle A }, 이웃 교차로로 연결된 도로의 길이를 B { displaystyle B }, 이웃 교차로에 쓰여 있는 거리를 C { displaystyle C } 라고 할 때, A B < C
] 단일 도착점의 경우의 데이크스트라 알고리즘을 더 최적화 한 것에는 양방향 변형이 있고, A * 알고리즘 같은 목적 지향 변형이 있으며 ( 관련 문제와 알고리즘 참고 ), 어떤 꼭짓점이 최단 경로의 일부를 이룰 것 같은지를 결정하기 위한 그래프 가지치기가 있으며 ( 도달 기반 라우팅 ), s와 t를 각각 " 고속도로 " 를 이용한 전이 꼭짓점 간의 최단 경로 계산에 의한 " 전이 꼭짓점 " 으로 연결시키기 위해서 s - t 라우팅을 감소시키는 입력된 그래프의 계급 분해를 사용할 수 있다. [ 14 ] 이러 기술을 결합하는 것은 특정 문제에서 실제 최적의 수행에 필요할 수 있다. [ 15 ] 세분화된 변형 [ 편집 ] 변의 비용이 작은 정수일 때 ( C 보다 작을 때 ), 데이크스트라 알고리즘의 속도를 높이기 위해서 단조 우선순위 큐를 쓸 수 있다. 이 종류의 첫 번째 알고리즘은 Dial's algorithm으로, 버켓 큐를 사용해서 수행 시간이 O ( | E | diam ( G ) ( G ) ) { displaystyle O ( | E | operatorname { diam } ( G ) ( G ) ) } 로, 정수 가중치를 갖는 그래프의 가중 지름에 의존한다 ( Dial 1969 ). 판엠
##M 》 53 ( 8 ) : 41 - 47. doi : 10. 1145 / 1787234. 1787249. ↑ 가 나 Dijkstra, E. W. ( 1959 ). " A note on two problems in connexion with graphs " ( PDF ). 《 Numerische Mathematik 》 1 : 269 - 271. doi : 10. 1007 / BF01386390. ↑ 가 나 다 Mehlhorn, Kurt ; Sanders, Peter ( 2008 ). 〈 Chapter 10. Shortest Paths 〉 ( PDF ). 《 Algorithms and Data Structures : The Basic Toolbox 》. Springer. ISBN 978 - 3 - 540 - 77977 - 3. doi : 10. 1007 / 978 - 3 - 540 - 77978 - 0. ↑ 가 나 Felner, Ariel ( 2011 ). 《 Position Paper : Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm 》. Proc. 4th Int'l Symp. on Combinatorial Search. ↑
##gorithm 》. Proc. 4th Int'l Symp. on Combinatorial Search. ↑ " ARMAC ". 《 Unsung Heroes in Dutch Computing History 》. 2007. 13 November 2013에 원본 문서에서 보존된 문서. ↑ Dijkstra, Edsger W., 《 Reflections on " A note on two problems in connexion with graphs 》 ( PDF ) ↑ Tarjan, Robert Endre ( 1983 ), 《 Data Structures and Network Algorithms 》, CBMS - NSF Regional Conference Series in Applied Mathematics 44, Society for Industrial and Applied Mathematics, 75쪽, The third classical minimum spanning tree algorithm was discovered by and rediscovered by Prim and Dikstra ; it is commonly known as Prim's algorithm. ↑ Prim, R. C. ( 1957 ). " Shortest connection networks and some generalizations " ( PDF ). 《 Bell System Technical Journal 》 36 : 138
) }. 이진 힙을 사용할 때, 평균 시간복잡도는 최악의 경우 보다 더 낮다 : 변의 비용이 일반적인 확률 분포와 무관하다고 가정하면, decrease - key 연산의 기대 연산 횟수의 상한은 O ( | V | log ( | E | / | V | ) ( | E | / | V | ) ) { displaystyle O ( | V | log ( | E | / | V | ) ( | E | / | V | ) ) } 이므로, 총 수행 시간은 다음과 같아진다 : [ 4 ] : 199 - 200 O ( | E | | V | log | E | | V | log | V | ) { displaystyle O left ( | E | | V | log { frac { | E | } { | V | } } log | V | right ) }. 게다가, 그래프에 있는 모든 꼭짓점을 삽입하지 않으면 알고리즘을 무한 그래프나 메모리로 표현하기에는 너무 큰 그래프에서 시작점에서 도착점까지의 최단 경로를 찾도록 확장할 수 있다. 그 결과로 나타나는 알고리즘은 인공지능 분야에서 균일 비용 탐색 ( UCS ) 이라고 불리고 [ 5 ] [ 12 ] [ 13 ] 다음의 의사 코드로 나타낼 수 있다 procedure
컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다.이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다. 그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다.:196-206 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS-IS (Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에서 주로 사용된다. 또한 데이크스트라 알고리즘은 존슨 알고리즘 같은 알고리즘의 서브루틴으로 채택되었다. 데이크스트라의 원래 알고리즘은 우선순위 큐를 사용하지 않았기 때문에 시간 복잡도가 O (| V | 2) {\displaystyle O(|V|^{2})} (| V | {\displaystyle |V|} 는 꼭짓점의 개수이다)이다. 이 알고리즘의 개념은 Leyzorek 등. 1957에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간복잡도는 Fredman & Tarjan 1984 때문에 O (| E | | V | log ⁡ | V |) {\displaystyle O(|E||V|\log |V|)} (| E | {\displaystyle |E|} 는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 유향 그래프에서의 단일 소스 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 § 세분화된 변형으로 개선할 수 있다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화되어있다.