icographic BFS LPA * 프림 SMA * 목록 그래프 알고리즘 탐색 알고리즘 그래프 알고리즘의 목록 관련 주제 동적 계획법 그래프 순회 트리 순회 Search game v. d. e. h 컴퓨터 과학에서, 데이크스트라 알고리즘 ( 영어 : Dijkstra algorithm ) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다. [ 1 ] [ 2 ] [ 3 ] 이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, [ 3 ] 더 일반적인 변형은 한 꼭짓점을 " 소스 " 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다. 그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다. [ 4 ] : 196 - 206 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식
earch ( Graph, start, goal ) node [UNK] start cost [UNK] 0 frontier [UNK] priority queue containing node only explored [UNK] empty set do if frontier is empty return failure node [UNK] 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 ) 이 알고리즘의 복잡성은 매우 큰 그래프에서 다른 방법으로 표현할 수 있다 : C * 가 시작점에서 " 도착 " 예측을 만족하는 어떤 점으로 가는 최단 경로의 길이라고 하고, 각각의 변이 적어도 [UNK] 비용이 들며, 꼭짓점의 인접 꼭짓점의 개수가 최대 b라고 한다면, 알고리즘의 최악의 경우와 공간복잡도는 둘 다 O ( b1 [UNK] C * [UNK] [UNK] [UNK] ) 이다. [ 12 ] 단일 도착점의 경우의 데이크스트라 알고리즘을 더 최적화 한 것에는 양방향 변형이 있고, A * 알고리즘 같은 목적 지향 변형이 있으며 ( [UNK] 관련 문제와 알고리즘 참고 ), 어떤 꼭짓점이 최단 경로의 일부를 이룰 것 같은지를 결정하기 위한 그래프 가지치기가
는다. [ 4 ] : 196 - 206 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 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에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간복잡도는
. 1 우선순위 큐 사용 5 정확성의 증명 6 실행 시간 6. 1 세분화된 변형 7 관련 문제와 알고리즘 7. 1 동적 계획법의 관점 8 같이 보기 9 참조 10 참고 문헌 11 외부 링크 역사 [ 편집 ] 로테르담에서 흐로닝언까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길은 무엇일까요 이것은 제가 이십 분 동안 생각해낸 최단 거리를 찾는 알고리즘입니다. 어느 날 아침에 저는 제 약혼녀와 암스테르담에서 쇼핑을 하고 있었고, 지쳤었기 때문에 카페 테라스에 앉아서 커피를 마시면서 그 문제에 대해서 생각하다가 최단 거리를 찾는 알고리즘을 고안했습니다. 제가 말했듯이, 이것은 이십 분 짜리 발명품입니다. 사실, 이 알고리즘은 삼 년 뒤인 59년에 발표했습니다. 그 간행물을 여전히 읽을 수 있습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다. - 에츠허르 데이
데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전 데이크스트라 알고리즘 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 데이크스트라 알고리즘 a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다. 분류 탐색 알고리즘자료 구조 그래프최악 시간복잡도 O ( | E | | V | log | V | ) { [UNK] displaystyle 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 컴퓨터 과학에서, 데이크스
에는 양방향 변형이 있고, A * 알고리즘 같은 목적 지향 변형이 있으며 ( [UNK] 관련 문제와 알고리즘 참고 ), 어떤 꼭짓점이 최단 경로의 일부를 이룰 것 같은지를 결정하기 위한 그래프 가지치기가 있으며 ( 도달 기반 라우팅 ), s와 t를 각각 " 고속도로 " 를 이용한 전이 꼭짓점 간의 최단 경로 계산에 의한 " 전이 꼭짓점 " 으로 연결시키기 위해서 s - t 라우팅을 감소시키는 입력된 그래프의 계급 분해를 사용할 수 있다. [ 14 ] 이러 기술을 결합하는 것은 특정 문제에서 실제 최적의 수행에 필요할 수 있다. [ 15 ] 세분화된 변형 [ 편집 ] 변의 비용이 작은 정수일 때 ( C 보다 작을 때 ), 데이크스트라 알고리즘의 속도를 높이기 위해서 단조 우선순위 큐를 쓸 수 있다. 이 종류의 첫 번째 알고리즘은 Dial's algorithm으로, 버켓 큐를 사용해서 수행 시간이 O ( | E | diam ( G ) ( G ) ) { [UNK] displaystyle O ( | E | [UNK] operatorname { diam } ( G ) ( G ) ) } 로, 정수 가중치를 갖는 그래프의 가중 지름에 의존한다 ( Dial 1969 ). 판엠더 보아스 트리를 우선순위 큐로 사용하면 복잡성은 O ( |
점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다. - 에츠허르 데이크스트라, Philip L과의 인터뷰에서. Frana, Communications of the ACM, 2001 [ 2 ] 데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다. [ 6 ] 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 ( 컴퓨터가 만들어낸 ) 해법을 둘 다 선택하는 것이었다. 그는 최단 거리 알고리즘을 고안하고, 이후 ARMAC에서 약간 단순화된 네덜란드 도시 64개 ( 도시의 숫자를 표시하기 위해서 6 비트만 필요하도록 64를 선정했다 ) 의 교통 지도에 대해서 수행했다. [ 2 ] 일 년 뒤, 데이크스트라는 기관의 다음 컴퓨터를 작업하던 하드웨어 엔지니어들의 문제를 직면했다 : 기계의 후면 패널에 있는 핀을 연결 할 때 필요한 전선의 개수를 최소화 하는 것이다. 그 해법으로, 프림 최소 신장 트리 알고리즘으로 알려진 알고리즘을 재발견 했다 ( 이전에는 [UNK] 의해 알려져 있었고, 또한 프림에 의해 재발견
이 여러 개였을 때, 새 그래프에서 그 꼭짓점에서 다른 꼭짓점으로 가는 모든 경로가 원래 그래프의 그 꼭짓점에서도 최단 경로라는 점과, 원본 그래프에서 그 길이를 가지는 모든 경로가 새로운 그래프에도 나타난다는 점이다. 실제로 주어진 두 꼭짓점 간의 최단 거리를 모두 찾기 위해서는 새로운 그래프에서 깊이 우선 탐색 같은 경로 찾기 알고리즘이 필요하다. 우선순위 큐 사용 [ 편집 ] 최소 우선 큐는 다음의 세 기본 연산을 제공하는 추상 자료형이다 : add - with - priority, decrease - priority 그리고 extract - min이다. 이전에 언급했듯이, 이런 자료구조를 사용하면 기본 큐를 사용하는 것 보다 계산 시간이 더 빨라질 수 있다. 특히, 피보나치 힙 ( Fredman & Tarjan 1984 ) 이나 브로들 큐는 이 3가지 연산에 대해서 최적의 수행을 제공한다. 알고리즘이 약간 다르기 때문에 아래에 의사 코드로 나타냈다 : 1 function Dijkstra ( Graph, source ) : 2 dist [ source ] [UNK] 0 / / 초기화 3 4 create vertex set Q 5 6 for each vertex v in Graph : 7 if v [UNK] source 8 dist [ v ] [UNK] IN
| V | log ( | E | / | V | ) ( | E | / | V | ) ) { [UNK] displaystyle O ( | V | [UNK] log ( | E | / | V | ) ( | E | / | V | ) ) } 이므로, 총 수행 시간은 다음과 같아진다 : [ 4 ] : 199 - 200 O ( | E | | V | log | E | | V | log | V | ) { [UNK] displaystyle O [UNK] left ( | E | | V | [UNK] log { [UNK] frac { | E | } { | V | } } [UNK] log | V | [UNK] right ) }. 게다가, 그래프에 있는 모든 꼭짓점을 삽입하지 않으면 알고리즘을 무한 그래프나 메모리로 표현하기에는 너무 큰 그래프에서 시작점에서 도착점까지의 최단 경로를 찾도록 확장할 수 있다. 그 결과로 나타나는 알고리즘은 인공지능 분야에서 균일 비용 탐색 ( UCS ) 이라고 불리고 [ 5 ] [ 12 ] [ 13 ] 다음의 의사 코드로 나타낼 수 있다 procedure UniformCostSearch ( Graph, start, goal ) node [UNK] start cost [UNK] 0 frontier [UNK] priority queue containing node only explored [UNK] empty set do
는 꼭짓점의 개수이다 ) 이다. 이 알고리즘의 개념은 Leyzorek 외. 1957에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간복잡도는 Fredman & Tarjan 1984 때문에 O ( | E | | V | log | V | ) { [UNK] displaystyle O ( | E | | V | [UNK] log | V | ) } ( | E | { [UNK] displaystyle | E | } 는 변의 개수이다 ) 이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 유향 그래프에서의 단일 소스 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우 ( 제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우 ) 에는 다른 [UNK] 세분화된 변형으로 개선할 수 있다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화 되어있다. [ 5 ] 목차 1 역사 2 알고리즘 3 설명 4 의사 코드 4. 1 우선순위 큐 사용 5 정확성의 증명 6 실행 시간 6. 1 세분화된 변형 7 관련 문제와 알고리즘 7. 1 동적 계획법의 관점 8 같이 보기 9 참조 10 참고 문헌 11 외부 링크 역사 [ 편집 ] 로
컴퓨터 과학에서 데이크스트라 알고리즘(영어: 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|} 는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 유향 그래프에서의 단일 소스 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 § 세분화된 변형으로 개선할 수 있다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화되어있다.