le O ( | E | | V | [UNK] log | V | ) } 그래프와 트리탐색 알고리즘 alpha - beta A * B * 퇴각검색 빔 벨먼 - 포드 최상 우선 양방향 [UNK] 분기 판정법 BFS 영국박물관 D * DFS 데이크스트라 에드먼즈 플로이드 - 워셜 Fringe search 언덕등반기법 IDA * 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA * 프림 SMA * 목록 그래프 알고리즘 탐색 알고리즘 그래프 알고리즘의 목록 관련 주제 동적 계획법 그래프 순회 트리 순회 Search game v. d. e. h 컴퓨터 과학에서, 데이크스트라 알고리즘 ( 영어 : Dijkstra algorithm ) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.
, 데이크스트라 알고리즘 ( 영어 : Dijkstra algorithm ) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다. [ 1 ] [ 2 ] [ 3 ] 이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, [ 3 ] 더 일반적인 변형은 한 꼭짓점을 " 소스 " 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다. 그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를
도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS - IS ( Intermediate System to Intermediate System ) 와 OSPF ( Open Shortest Path First ) 에서 주로 사용된다. 또한 데이크스트라 알고리즘은 존슨 알고리즘 같은 알고리즘의 서브루틴으로 채택되었다. 데이크스트라의 원래 알고리즘은 최소 우선 큐를 사용하지 않았기 때문에 시간 복잡도가 O ( | V | 2 ) { [UNK] displaystyle O ( | V | ^ { 2 } ) } ( | V | { [UNK] displaystyle | V | } 는 꼭짓점의 개수이다 ) 이다. 이 알고리즘의 개념은 Leyzorek 외. 1957에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간
까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다. 그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다. [ 4 ] : 196 - 206 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS - IS ( Intermediate System to Intermediate System ) 와 OSPF
습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다. - 에츠허르 데이크스트라, Philip L과의 인터뷰에서. Frana, Communications of the ACM, 2001 [ 2 ] 데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다. [ 6 ] 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 ( 컴퓨터가
하는 어떤 점으로 가는 최단 경로의 길이라고 하고, 각각의 변이 적어도 [UNK] 비용이 들며, 꼭짓점의 인접 꼭짓점의 개수가 최대 b라고 한다면, 알고리즘의 최악의 경우와 공간복잡도는 둘 다 O ( b1 [UNK] C * [UNK] [UNK] [UNK] ) 이다. [ 12 ] 단일 도착점의 경우의 데이크스트라 알고리즘을 더 최적화 한 것에는 양방향 변형이 있고, A * 알고리즘 같은 목적 지향 변형이 있으며 ( [UNK] 관련 문제와 알고리즘 참고 ), 어떤 꼭짓점이 최단 경로의 일부를 이룰 것 같은지를 결정하기 위한 그래프 가지치기가 있으며 ( 도달 기반 라우팅 ), s와 t를 각각 " 고속도로 " 를 이용한 전이 꼭짓점 간의 최단 경로 계산에 의한 " 전이 꼭짓점 " 으로 연결시키기 위해서 s - t 라우팅을 감소시키는 입력된 그래프의 계급 분해를 사용할 수 있다
최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우 ( 제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우 ) 에는 다른 [UNK] 세분화된 변형으로 개선할 수 있다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화 되어있다. [ 5 ] 목차 1 역사 2 알고리즘 3 설명 4 의사 코드 4. 1 우선순위 큐 사용 5 정확성의 증명 6 실행 시간 6. 1 세분화된 변형 7 관련 문제와 알고리즘 7. 1 동적 계획법의 관점 8 같이 보기 9 참조 10 참고 문헌 11 외부 링크 역사 [ 편집 ] 로테르담에서 흐로닝언까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길은 무엇일까요 이것은 제가 이십 분 동안 생각해낸 최단 거리를 찾는
ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다. [ 6 ] 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 ( 컴퓨터가 만들어낸 ) 해법을 둘 다 선택하는 것이었다. 그는 최단 거리 알고리즘을 고안하고, 이후 ARMAC에서 약간 단순화된 네덜란드 도시 64개 ( 도시의 숫자를 표시하기 위해서 6 비트만 필요하도록 64를 선정했다 ) 의 교통 지도에 대해서 수행했다. [ 2 ] 일 년 뒤, 데이크스트라는 기관의 다음 컴퓨터를 작업하던 하드웨어 엔지니어들의 문제를 직면했다 : 기계의 후면 패널에 있는 핀을 연결 할 때 필요한 전선의 개수를 최소화 하는 것이다. 그 해법으로, 프림 최소 신장 트리 알고리즘으로 알려진 알고리즘을 재발견 했다 ( 이전에는 [UNK] 의해 알려져 있었고
그 꼭짓점에서도 최단 경로라는 점과, 원본 그래프에서 그 길이를 가지는 모든 경로가 새로운 그래프에도 나타난다는 점이다. 실제로 주어진 두 꼭짓점 간의 최단 거리를 모두 찾기 위해서는 새로운 그래프에서 깊이 우선 탐색 같은 경로 찾기 알고리즘이 필요하다. 우선순위 큐 사용 [ 편집 ] 최소 우선 큐는 다음의 세 기본 연산을 제공하는 추상 자료형이다 : add - with - priority, decrease - priority 그리고 extract - min이다. 이전에 언급했듯이, 이런 자료구조를 사용하면 기본 큐를 사용하는 것 보다 계산 시간이 더 빨라질 수 있다. 특히, 피보나치 힙 ( Fredman & Tarjan 1984 ) 이나 브로들 큐는 이 3가지 연산에 대해서 최적의 수행을 제공한다. 알고리즘이 약간 다르기 때문에 아래에 의사 코드로 나타냈다 : 1 fun
있다. 최적 이하의 해법의 순위표를 얻기 위해서는 먼저 최적 해법을 계산해야 한다. 최적 해법의 한 변을 그래프에서 제거하고, 이 새로운 그래프에서 최적 해법을 계산한다. 원래 해법의 각각의 변을 차례로 제거하고 새로운 최단 경로를 계산한다. 그러면 두 번째 해법을 순위매기고 첫 번째 최적 해법의 다음에 표시한다. 데이크스트라 알고리즘은 종종 링크 상태 라우팅 프로토콜의 원리에 의해 작동하며, OSPF와 IS - IS가 그중 가장 일반적인 것이다. 데이크스트라 알고리즘과는 달리, 벨먼 - 포드 알고리즘은 소스 꼭짓점 s에서 도달할 수 있는 음수 사이클이 없으면 음수 가중치가 있을 때에도 사용할 수 있다. 이런 사이클이 존재하면, 이 사이클에 들어가서 한 바퀴를 돌 때 마다 전체 비용이 감소하기 때문에 최단 경로가 없다. 데이크스트라 알고리즘에 (
컴퓨터 과학에서 데이크스트라 알고리즘(영어: 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|} 는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 유향 그래프에서의 단일 소스 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 § 세분화된 변형으로 개선할 수 있다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화되어있다.