다이크스트라의 알고리즘

다이크스트라의 알고리즘

a와 b 사이의 최단 경로를 찾는 Dijkstra의 알고리즘. 가장 낮은 거리를 가진 방문하지 않은 정점을 선택하고, 이를 통해 방문하지 않은 각 이웃까지의 거리를 계산하고, 더 작으면 이웃의 거리를 업데이트합니다. 이웃과 함께 작업을 마치면 마크가 방문(빨간색으로 설정)했습니다.
학급	검색 알고리즘 그리디 알고리즘 동적 프로그래밍[1]
자료구조	그래프 일반적으로 최적화를[2][3] 위해 우선 순위 대기열 또는 힙과 함께 사용됨
최악의 경우 성능	${\displaystyle \Theta(E + V \log V )}$[3]

Dijkstra의 알고리즘(/ ˈda ɪkstr əz/ DYKE-str əz)은 가중 그래프에서 노드 간 최단 경로를 찾는 알고리즘으로, 예를 들어 도로 네트워크를 나타낼 수 있습니다. 1956년 컴퓨터 과학자 에드거 데이크스트라(Edsger W. Dijkstra)에 의해 구상되어 3년 후에 출판되었습니다.^[4][5][6]

알고리즘은 다양한 변형으로 존재합니다. Dijkstra의 원래 알고리즘은 주어진 두 노드 사이에서 가장 짧은 경로를 ^[6]찾았지만 더 일반적인 변형은 단일 노드를 "소스" 노드로 고정하고 소스에서 그래프의 다른 모든 노드로 가장 짧은 경로를 찾아 최단 경로 트리를 생성합니다.

그래프에서 주어진 소스 노드에 대해 알고리즘은 해당 노드와 다른 노드 사이의 최단 경로를 찾습니다.^{[7]: 196–206} 목적지 노드로의 최단 경로가 결정되면 알고리즘을 중지하여 단일 노드에서 단일 목적지 노드로의 최단 경로를 찾는 데에도 사용할 수 있습니다. 예를 들어, 그래프의 노드가 도시를 나타내고 에지 경로의 비용이 직접 도로로 연결된 도시 쌍 간의 주행 거리를 나타내는 경우(간단히 설명하기 위해 적색등, 정지표지, 유료도로 및 기타 장애물은 무시), Dijkstra 알고리즘을 사용하여 한 도시와 다른 모든 도시 간의 최단 경로를 찾을 수 있습니다. 네트워크 라우팅 프로토콜은 IS-IS(Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)로 널리 사용됩니다. 존슨의 알고리즘과 같은 다른 알고리즘에서도 서브루틴으로 사용됩니다.

Dijkstra 알고리즘은 완전히 순서화된 양의 정수 또는 실수인 레이블을 사용합니다. 후속 레이블(엣지를 횡단할 때 후속 레이블이 생성됨)이 단조적으로 감소하지 않는 경우, 부분적으로 순서가 지정된 모든 레이블을 사용하는 것이 일반화될 수 있습니다. 이러한 일반화를 일반적인 Dijkstra 최단 경로 알고리즘이라고 합니다.^[8][9]

Dijkstra의 알고리즘은 시작부터 거리별로 정렬된 부분 솔루션을 저장하고 조회하기 위한 데이터 구조를 사용합니다. Dijkstra의 원래 알고리즘은 min-priority 큐를 사용하지 않으며${\displaystyle {}^{}}$θ(V 2$)$ ${\displaystyle \Theta($V$$^{2})}($여기$서${\displaystyle }$V ${\displaystyle$ V}는 노드 수)에서 실행됩니다. 이 알고리즘의 아이디어는 Leyzorek et al. 1957에도 나와 있습니다. Fredman & Tarjan 1984는 실행 시간 복잡성을${\displaystyle }$θ(${\displaystyle E}$ +${\displaystyle }$V ${\displaystyle log}$⁡ V)${\displaystyle \Theta($E + V \log V )}로 최적화하기 위해 Fibonacci 힙 최소 우선 순위 대기열을 사용할 것을 제안합니다. 이것은 무제한의 음이 아닌 가중치를 가진 임의의 지시된 그래프에 대해 점근적으로 가장 빠른 단일 소스 최단 경로 알고리즘입니다. 그러나 특수한 경우(예: 유계/정수 가중치, 방향 비순환 그래프 등)는 실제로 특수한 변형에 자세히 설명된 것처럼 더 개선될 수 있습니다. 또한, 사전 처리가 허용되는 경우, 수축 계층과 같은 알고리즘은 최대 7차수 더 빨라질 수 있습니다.

일부 분야에서는 특히 Dijkstra의 알고리즘 또는 그 변형을 균일한 비용 검색이라고 하며, 더 일반적인 베스트 퍼스트 검색 개념의 사례로 공식화합니다.^[11]

역사

로테르담에서 흐로닝언까지, 일반적으로, 주어진 도시에서 주어진 도시로 이동하는 가장 짧은 방법은 무엇입니까? 가장 짧은 경로에 대한 알고리즘인데, 약 20분 만에 설계했습니다. 어느 날 아침 저는 젊은 약혼자와 암스테르담에서 쇼핑을 하고 있었는데, 피곤해서 카페 테라스에 앉아서 커피를 한 잔 마셨는데, 제가 이걸 할 수 있을까 고민하다가, 가장 짧은 길에 대한 알고리즘을 고안해 냈습니다. 제가 말했듯이, 그것은 20분짜리 발명품이었습니다. 사실, 그것은 3년 후인 59년에 출판되었습니다. 출판물은 여전히 읽을 수 있고, 사실 꽤 좋습니다. 너무 좋은 이유 중 하나는 연필과 종이 없이 디자인한 것입니다. 연필과 종이가 없는 디자인의 장점 중 하나는 피할 수 없는 복잡성을 거의 피할 수 없다는 것을 나중에 알게 되었습니다. 결국, 그 알고리즘은 제 명성의 초석 중 하나인 저에게 큰 놀라움을 안겨주었습니다.

— Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001^[5]

Dijkstra는 1956년 ARMAC이라는 새로운 컴퓨터의 능력을 입증하기 위해 암스테르담의 Mathematical Center에서 프로그래머로 일하면서 최단 경로 문제에 대해 생각했습니다.^[12] 그의 목표는 컴퓨터를 사용하지 않는 사람들이 이해할 수 있는 문제와 해결책을 선택하는 것이었습니다. 그는 최단 경로 알고리즘을 설계하고 나중에 네덜란드 64개 도시의 약간 단순화된 교통 지도를 위해 ARMAC를 위해 구현했습니다(64, 6비트로 도시 번호를 인코딩하기에 충분합니다).^[5] 1년 후, 그는 연구소의 다음 컴퓨터를 작업하고 있는 하드웨어 엔지니어들로부터 기계의 후면 패널에 있는 핀들을 연결하는 데 필요한 와이어의 양을 최소화하는 또 다른 문제를 발견했습니다. 그 해결책으로 프림의 최소 스패닝 트리 알고리즘(이전에는 Jarník로 알려져 있었고 프림에 의해 재발견되기도 함)이라는 알고리즘을 재발견했습니다.^[13][14] Dijkstra는 1959년에 알고리즘을 발표했는데, Prim 이후 2년, Jarník 이후 29년 뒤였습니다.^[15][16]

알고리즘.

시작하는 노드를 초기 노드라고 합니다. 노드 Y의 거리를 초기 노드에서 Y까지의 거리라고 합니다. Dijkstra의 알고리즘은 처음에는 무한한 거리에서 시작하여 단계적으로 개선하려고 노력할 것입니다.

1. 모든 노드를 방문하지 않음으로 표시합니다. 방문하지 않은 집합이라고 하는 모든 방문하지 않은 노드 집합을 만듭니다.
2. 모든 노드에 잠정적인 거리 값을 할당합니다. 초기 노드에 대해서는 0으로 설정하고 다른 모든 노드에 대해서는 무한으로 설정합니다. 알고리즘을 실행하는 동안 노드 v의 잠정적인 거리는 노드 v와 시작 노드 사이에서 지금까지 발견된 가장 짧은 경로의 길이입니다. 처음에는 소스 자체 이외의 다른 정점에 대한 경로가 알려져 있지 않기 때문에(길이 0의 경로), 다른 모든 잠정 거리는 처음에 무한대로 설정됩니다. 초기 노드를 전류로 설정합니다.^[17]
3. 현재 노드의 경우 방문되지 않은 모든 이웃을 고려하고 현재 노드를 통과하는 잠정적인 거리를 계산합니다. 새로 계산된 잠정 거리를 현재 이웃에게 할당된 잠정 거리와 비교하여 더 작은 거리를 할당합니다. 예를 들어, 현재 노드 A가 거리 6으로 표시되어 있고, 그것을 이웃 B와 연결하는 간선의 길이가 2라면, A를 통해 B까지의 거리는 6 + 2 = 8이 될 것입니다. 이전에 B가 8보다 큰 거리로 표시되어 있었다면 8로 변경합니다. 그렇지 않으면 현재 값이 유지됩니다.
4. 현재 노드의 모든 방문되지 않은 이웃을 고려한 작업이 완료되면 현재 노드를 방문된 것으로 표시하고 방문되지 않은 집합에서 제거합니다. 방문한 노드는 다시 확인되지 않습니다(이것은 6단계의 동작과 관련하여 유효하고 최적입니다. 즉, 방문할 다음 노드는 항상 '처음 노드에서 가장 작은 거리'의 순서로 있으므로 이후 방문한 노드는 더 큰 거리를 가집니다.).
5. 대상 노드가 방문(두 개의 특정 노드 사이의 경로를 계획할 때) 표시되었거나 방문하지 않은 집합의 노드 중 가장 작은 잠정 거리가 무한대인 경우(완전한 횡단을 계획할 때; 초기 노드와 방문하지 않은 나머지 노드 사이에 연결이 없을 때 발생) 중지됩니다. 알고리즘이 완료되었습니다.
6. 그렇지 않으면 잠정 거리가 가장 작은 값으로 표시된 방문하지 않은 노드를 선택하고 새 현재 노드로 설정한 후 3단계로 돌아갑니다.

경로를 계획할 때, 위와 같이 목적지 노드가 "방문"될 때까지 기다릴 필요가 없습니다. 알고리즘은 목적지 노드가 모든 "방문되지 않은" 노드들 중에서 가장 작은 잠정적인 거리를 가지면 중지할 수 있습니다(따라서 다음 "현재"로 선택될 수 있습니다).

묘사

도시 지도에서 출발점과 도착지의 두 교차점 사이의 가장 짧은 경로를 찾고자 한다고 가정합니다. Dijkstra의 알고리즘은 처음에 지도의 다른 모든 교차점까지의 거리를 무한대로 표시합니다. 이것은 무한한 거리가 있다는 것을 암시하는 것이 아니라, 그 교차로들이 아직 방문되지 않았다는 것을 주목하기 위해 수행됩니다. 이 방법의 일부 변형은 교차로의 거리를 레이블로 지정하지 않습니다. 이제 각 반복에서 현재 교차점을 선택합니다. 첫 번째 반복의 경우 현재 교차점이 시작점이 되고 교차점까지의 거리(교차점의 레이블)는 0이 됩니다. 후속 반복(첫 번째 이후)의 경우, 현재 교차로는 시작점과 가장 가까운 비방문 교차로가 됩니다(이 교차로는 쉽게 찾을 수 있습니다).

현재 교차로에서 직접 연결된 모든 비방문 교차로까지의 거리를 업데이트합니다. 이는 비방문 교차로의 거리와 현재 교차로의 값의 합을 구한 후 비방문 교차로의 현재 값보다 작은 경우 이 값(합)으로 비방문 교차로를 재라벨하는 방법으로 수행됩니다. 실제로 교차로는 현재 교차로를 통과하는 경로가 이전에 알려진 경로보다 짧으면 다시 표시됩니다. 최단 경로 식별을 용이하게 하기 위해 연필로 레이블/라벨을 지정한 경우 레이블이 지정된 교차점을 가리키는 화살표로 도로를 표시하고 해당 교차점을 가리키는 다른 모든 것을 지웁니다. 이웃하는 각 교차로까지의 거리를 업데이트한 후 현재 교차로를 방문한 것으로 표시하고 (시작점에서) 최소 거리(또는 가장 낮은 레이블)가 있는 비방문 교차로를 현재 교차로로 선택합니다. 방문한 것으로 표시된 교차로에는 시작 지점에서 교차로까지의 최단 경로가 표시되며, 다시 방문하거나 되돌아가지 않습니다.

이 프로세스를 계속 진행하여 가장 짧은 거리를 가진 이웃 교차로를 업데이트하고 현재 교차로를 방문한 것으로 표시한 다음 대상을 방문한 것으로 표시할 때까지 가장 가까운 비방문 교차로로 이동합니다. 목적지를 방문한 것으로 표시하고 나면(방문한 교차로의 경우와 마찬가지로) 출발점에서 목적지로 가는 최단 경로를 결정하고 화살표를 거꾸로 따라 되돌아오는 길을 추적할 수 있습니다. 알고리즘의 구현에서, 이것은 보통 (알고리즘이 목적지 노드에 도달한 후) 목적지 노드에서 시작 노드까지 노드의 부모를 따라서 수행됩니다. 그래서 우리는 또한 각 노드의 부모를 추적합니다.

이 알고리즘은 예상대로 목적지를 향해 직접적인 "탐험"을 시도하지 않습니다. 오히려 다음 "현재" 교차점을 결정할 때 고려해야 할 유일한 사항은 출발점으로부터의 거리입니다. 따라서 이 알고리즘은 출발점에서 바깥쪽으로 확장되며, 목적지에 도달할 때까지 최단 경로 거리 측면에서 더 가까운 모든 노드를 상호 작용적으로 고려합니다. 이렇게 이해하면 알고리즘이 반드시 가장 짧은 경로를 찾는 방법이 분명합니다. 그러나 일부 토폴로지에서 상대적으로 느리다는 알고리즘의 단점 중 하나도 드러날 수 있습니다.

의사코드

다음 의사코드 알고리즘에서, dist는 에서 다른 정점까지의 현재 거리를 포함하는 배열입니다. 즉 dist[]u는 소스에서 정점까지의 현재 거리입니다. 사전 배열에는 소스에서 주어진 정점으로 가는 가장 짧은 경로의 이전 홉 노드에 대한 포인터가 포함됩니다(동등하게, 주어진 정점에서 소스로 가는 경로의 다음 홉입니다). 최소 dist[u] 값을 갖는 Q의 코드 u ← 정점은 가장 작은 dist[] 값을 갖는 정점 집합에서 정점을 검색합니다. 그래프.Edges(,u )는 두 인접 노드와 에 결합하는 에지의 길이(즉, 사이의 거리)를 반환합니다. 14번 행의 변수는 루트 노드에서 이웃 노드로 가는 경로의 길이입니다. 만약 이 경로가 에 기록된 현재 최단 경로보다 짧다면 현재 경로는 이 경로로 대체됩니다.^[7]

 1 함수 Dijkstra(그래프, 소스): 그래프의 각 정점 v에 대한 23.정점: Q 7 dist[v] ← INFINITY 5 prev[v] ← UNDEFINED 6은 Q 7 dist[source]에 v를 추가하고 Q는 비어 있지 않습니다. Q의 10 u ← 정점은 min dist[u] 11은 Q: 14 alt ← dist[u] + 그래프에 있는 u의 각 이웃 v에 대해 Q 1213에서 u를 제거합니다.가장자리(u, v) 15(alt < dist[v]인 경우): 16 dist[v] ← alt 17 prev[v] ← u 18 19 return dist[], prev[] 

만약 우리가 정점과 정점 사이의 최단 경로에만 관심이 있다면 =이면 행 10 이후의 검색을 종료할 수 있습니다. 이제 우리는 역반복을 통해 에서 로의 최단 경로를 읽을 수 있습니다.

prev[u]가 정의된 경우 1 S ← 빈 시퀀스 2 u ← target 3 또는 u = source: // u가 정의된 상태에서 정점이 4에 도달할 경우에만 수행: // S // 스택 S 5 insert u로 최단 경로를 구성합니다. 스택 6 u ← prev[u] // 대상에서 소스로 이동 

now sequence는 ~ 에서 가장 짧은 경로 중 하나를 구성하는 정점의 목록이거나 경로가 없는 경우 빈 시퀀스입니다.

보다 일반적인 문제는 와 사이의 최단 경로를 모두 찾는 것입니다(같은 길이의 다른 경로가 여러 개 있을 수 있습니다). 그런 다음 prev[]의 각 항목에 하나의 노드만 저장하는 대신 완화 조건을 충족하는 모든 노드를 저장합니다. 예를 들어, 연결과 연결 모두가 서로 다른 최단 경로에 있는 경우(엣지 비용은 두 경우 모두 동일하므로), prev[]target에 둘 다 추가합니다. 알고리즘이 완료되면 prev[] 데이터 구조는 일부 간선이 제거된 원래 그래프의 부분 집합인 그래프를 실제로 설명합니다. 알고리즘이 일부 시작 노드로 실행되면 해당 노드에서 새 그래프의 다른 노드까지의 모든 경로가 원래 그래프의 해당 노드 사이에서 가장 짧은 경로가 되고 원래 그래프에서 해당 길이의 모든 경로가 새 그래프에 표시됩니다. 그런 다음 주어진 두 노드 사이의 이 모든 최단 경로를 실제로 찾기 위해 깊이 우선 검색과 같은 새 그래프의 경로 찾기 알고리즘을 사용할 것입니다.

우선 순위 대기열 사용

min-priority 큐는 add_with_priority(), decry_priority() 및 extract_min()의 세 가지 기본 작업을 제공하는 추상 데이터 유형입니다. 앞서 언급한 바와 같이 이러한 데이터 구조를 사용하면 기본 큐를 사용하는 것보다 더 빠른 컴퓨팅 시간을 얻을 수 있습니다. 특히 피보나치 힙 또는^[18] 브로달 큐는 이러한 3가지 작업에 최적의 구현을 제공합니다. 알고리즘이 약간 다르기 때문에, 의사 코드에서도 다음과 같이 언급됩니다.

1 함수 Dijkstra(그래프, 소스): 2 dist[source] ← 0 // 초기화 34 그래프의 각 정점 v에 대해 정점 우선 순위 큐 Q 56을 만듭니다.정점: v ≠ 소스 8 dist[v] ← INFINITY // 소스에서 v 9 prev[v] ← UNDEFINED // v10 11 Q.add_with_priority(v, dist[v]) 12 1314 Q가 비어 있지 않은 동안: // 메인 루프 15 u ← Q.extract_min() // u의 각 이웃 v에 대해 best vertex 16을 제거하고 반환합니다: // u 17 alt ← dist[u] + Graph의 모든 v 이웃을 확인합니다.Edges(u, v) 18 if alt < dist[v]: 19 dist[v] ← alt 20 prev[v] ← u 21 Q.decrease_priority(v, alt) 22 23 return dist, prev 

초기화 단계에서 우선순위 대기열을 모든 노드로 채우는 대신 소스만 포함하도록 초기화할 수도 있습니다. 그런 다음 if alt < dist[v] 블록, 노드가 아직 큐에 없는 경우 decrease_priority ()는 add_with_priority () 작업이 됩니다.

또 다른 방법은 우선 순위 대기열에 무조건 노드를 추가하고 대신 추출 후 다시 방문하지 않거나 아직 더 짧은 연결이 발견되지 않았는지 확인하는 것입니다. 연결된 우선 순위를 추가로 추출하여 수행할 수 있습니다. p 대기열에서 더 이상의 처리만 수행합니다. if p == dist[u] 안쪽에 while Q is not empty 고리 모양의

이러한 대안은 감소 키 기능 없이 어레이 기반 우선 순위 대기열을 전체적으로 사용할 수 있으며, 이는 실제로 훨씬 더 빠른 컴퓨팅 시간을 달성하는 것으로 나타났습니다. 그러나 밀도가 높은 그래프일수록 성능의 차이가 더 좁은 것으로 나타났습니다.^[20]

정확성 증명

이 섹션에서는 출처를 인용하지 않습니다. 신뢰할 수 있는 출처에 인용을 추가하여 이 섹션을 개선하는 데 도움을 주세요. 출처가 없는 재료는 문제가 발생하여 제거될 수 있습니다. 출처 찾기 : "Dijkstra의 알고리즘" – 뉴스 · 신문 · 서적 · 학자 · JSTOR (2022년 12월) (본 템플릿 메시지 제거 방법 및 시기에 대해 알아보기)

Dijkstra 알고리즘의 증명은 방문한 노드의 수에 대한 귀납법에 의해 구성됩니다.

불변 가설: 방문한 각 노드 v에 대해, dist[v] 는 소스에서 v까지의 최단 거리이며, 방문하지 않은 각 노드 u에 대하여, dist[u] 는 방문한 노드만을 통해 이동할 때 소스에서 u까지의 최단 거리이거나, 그러한 경로가 없는 경우 무한대입니다. (참고: 가정하지 않음) dist[u] 방문하지 않은 노드의 실제 최단 거리인 반면 dist[v] 실제 최단거리)

기본 사례는 방문한 노드가 하나뿐인 경우, 즉 초기 노드 소스입니다. 이 경우 가설은 사소한 것입니다.

다음으로, k-1개의 방문 노드에 대한 가설을 가정합니다. 다음으로 알고리즘에 따라 다음 방문 노드로 우리를 선택합니다. 우리는 그것을 주장합니다. dist[u] 소스에서 당신까지의 최단 거리입니다.

그 주장을 증명하기 위해 모순에 의한 증명을 진행할 것입니다. 더 짧은 경로가 있는 경우, 가장 짧은 경로에 다른 방문되지 않은 노드가 포함되거나 포함되지 않는 두 가지 경우가 있을 수 있습니다.

첫 번째 경우, 가장 짧은 경로의 첫 번째 방문하지 않은 노드가 되겠습니다. 유도 가설에 따르면 소스에서 u로, 그리고 방문한 노드를 통과하는 최단 경로는 비용만 있습니다. dist[u] 그리고. dist[w] 각각 다음과 같다. 즉, 소스에서 w로 이동하는 비용은 적어도 다음과 같습니다. dist[w] + 우리에서 우리로 가는 데 드는 최소한의 비용 에지 비용이 양수이므로 w에서 u로 이동하는 최소 비용은 양수입니다.

또한. dist[u] < dist[w] 알고리즘이 w 대신 널 골랐기 때문입니다.

지금 우리는 다음과 같은 모순에 도달했습니다. dist[u] < dist[w] 아직 dist[w] + 양수 < dist[u].

두 번째 경우에는, 가장 짧은 경로에 있는 하나의 노드를 제외한 마지막 노드라고 가정합니다. 그 말은. dist[w] + Graph.Edges[w,u] < dist[u]. 그것은 모순입니다. 왜냐하면 우리가 방문할 때까지, 그것은 설정을 했어야 했기 때문입니다. dist[u] 기껏해야 dist[w] + Graph.Edges[w,u].

다른 모든 방문한 노드 v에 대해서는 귀납 가설이 우리에게 말해주었습니다. dist[v] 는 소스로부터 이미 최단 거리이며 알고리즘 단계는 그것을 변경하지 않습니다.

처리한 후에도 방문하지 않은 각 노드 w에 대해, dist[w] 당신이 가지 않는 더 짧은 경로가 있었다면 이전에 찾았을 것이고, 당신을 사용하는 더 짧은 경로가 있었다면 당신을 처리할 때 업데이트했을 것이기 때문에 오직 방문한 노드를 사용하여 소스에서 w까지의 최단 거리가 될 것입니다.

모든 노드가 방문된 후 소스에서 모든 노드 v까지의 최단 경로는 방문된 노드로만 구성되므로 dist[v] 가장 짧은 거리입니다.

러닝타임

간선 E와 정점 V가 있는 그래프에서 Dijkstra 알고리즘의 실행 시간의 경계는 빅-O 표기법을$$사용하여 ${\displaystyle E}$ $displaystyle E}$로 표시된 간선 수와$$V $displaystyle V}$로 표시된 정점 수의 함수로 표현할 수 있습니다. 복잡도 한계는 주로 집합 Q를 나타내는 데 사용되는 데이터 구조에 따라 달라집니다. 다음은 ${\displaystyle E}$ $displaystyle E}$가 임의의 단순 그래프에 $대해$ O${\displaystyle ({}^{\mathrm{}}}$ 2${\displaystyle {}^{}}$ ${\displaystyle$ O$(V ^{2})}$이기 때문에 상한을 단순화할 수 있지만, 단순화는 $문제$에서 E ${\displaystyle$ E}의 다른 상한이$$ 유지될 수 있다는 사실을 무시합니다.

정점 집합 Q에 대한 임의의 데이터 구조의 경우, 실행 시간은^[2]

${\displaystyle \Theta(E \cdot T_{\mathrm {dk}}+ V \cdot T_{\mathrm {em}),}$

$여기$서 ${\displaystyle {\mathrm{Tdk}}_{}}$ ${\$ 및 ${\displaystyle {\mathrm{Tem<img\; alt="T\_\{\backslash mathrm\; \{dk\}\; \}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline\; mw-invert"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/9d472cd5eeba8435ca78f0662c29f549a6e68758"\; style="vertical-align:\; -0.671ex;\; width:3.372ex;\; height:2.509ex;">}}_{}}$ ${\$는 각각 Q의 감소 키 및 추출 최소 연산의 복잡도입니다$$.

가장 간단한 버전의 Dijkstra 알고리즘은 정점 집합 Q를 연결된 목록 또는 배열로 저장하고, 에지를 인접 목록 또는 행렬로 저장합니다. 이 경우 extract- minimum는 단순히 Q의 모든 정점을 통한 선형 검색이므로 실행 $시간$은${\displaystyle }$θ$$θ (E + V 2) = θ (V 2)${\$displaystyle \Theta (E + V ^{2})=$\Theta ( V ^{2})}$.

희소 그래프, 즉 ${\displaystyle {}^{\mathrm{}}}$ ${\$ V$^{2}}$개보다$$ 훨씬 적은 에지를 갖는 그래프의 경우, 그래프를 인접 리스트의 형태로 저장하고 셀프-밸런싱 바이너리 검색 트리, 바이너리 힙, 페어링 힙을 사용하여 Dijkstra의 알고리즘을 보다 효율적으로 구현할 수 있습니다. 또는 최소 추출을 효율적으로 구현하기 위한 우선 순위 대기열로서 피보나치 힙. 이진 힙에서 감소 키 단계를 효율적으로 수행하기 위해서는 각 정점을 힙 내 위치에 매핑하는 보조 데이터 구조를 사용해야 하며, 우선 순위 큐 Q가 변경됨에 따라 이 구조를 최신 상태로 유지해야 합니다. 자기 균형 이진 검색 트리 또는 이진 힙을 사용하는 알고리즘은 다음과 같이 요구합니다.

${\displaystyle \Theta((E + V))\log V )}$

최악의 경우 연결된 그래프의 경우 이 시간 바운드는${\displaystyle }$θ$$⁡${\displaystyle (}$E 로그 ⁡ V) {\$displaystyle$ \$Theta$E 로그 V )}로 단순화될 수 있습니다. Fibonacci 힙은 이 기능을 다음으로 향상시킵니다.

${\displaystyle \Theta(E + V \log V )}$

이진 힙을 사용하는 경우 평균 케이스 시간 복잡도가 최악의 경우보다 낮습니다. 에지 비용이 공통 확률 분포와 독립적으로 그려진다고 가정하면 예상되는 감소 키 작업 수는${\displaystyle }$θ$$⁡${\displaystyle (V}$로그${\displaystyle }$⁡(E / V)) ${\displaystyle \Theta($V$$\log(E / V))}, 총^{[7]: 199–200} 실행 시간을 주기 위해

${\displaystyle O\left(E + V \log {\frac {E}{V}}\log V \right)}.$

실용적인 최적화 및 무한 그래프

Dijkstra 알고리즘의 일반적인 프레젠테이션에서는 처음에 모든 노드가 우선 순위 대기열에 입력됩니다. 그러나 이것은 필요하지 않습니다. 알고리즘은 하나의 항목만 포함된 우선 순위 대기열에서 시작하여 검색할 때 새 항목을 삽입할 수 있습니다(감소 키 대신에 키가 대기열에 있는지 확인하고 키를 줄이면 키를 줄이면 삽입).^{[7]: 198} 이 변형은 일반적인 변형과 동일한 최악의 경우 경계를 갖지만 실제로는 더 작은 우선 순위 대기열을 유지하여 대기열 작업 속도를 높입니다.^[11]

또한 그래프에 모든 노드를 삽입하지 않으면 알고리즘을 확장하여 무한 그래프 또는 메모리에서 표현하기에 너무 큰 대상 노드 집합에 가장 가까운 단일 소스에서 가장 짧은 경로를 찾을 수 있습니다. 결과적인 알고리즘은 인공지능 문헌에서^[11][21][22] UCS(Uniform-Cost Search)라고 불리며 의사 코드로 표현할 수 있습니다.

procedure uniform_cost_search(start)는 node ← start frontier ← node only expansed를 포함하는 priority queue ← frontier가 비어 있는 경우 빈 set do, node가 목표 상태인 경우 return failure node ← frontier.pop (), node가 목표 상태인 경우 return solution(node).n이 확장되지 않고 프론티어가 아닌 경우 노드의 각 이웃 n에 대해 add(node)를 수행합니다. n이 더 높은 비용으로 프론티어에 있는 경우 n이 기존 노드를 n으로 대체합니다. 

이 알고리즘의 복잡성은 매우 큰 그래프에 대한 대안적인 방법으로 표현될 수 있습니다: C가 시작 노드에서 "목표" 술어를 만족하는 노드까지의 최단 경로의 길이일 때, 각 에지는 적어도 ε의 비용이 들고 노드당 이웃의 수는 b로 제한됩니다. 그런 다음 알고리즘의 최악의 시간과 공간 복잡도는 모두 O(b^{1+⌊C* ⁄ ε⌋})에 있습니다.^[21]

단일 대상 사례에 대한 Dijkstra의 알고리즘의 추가 최적화에는 양방향 변형, A* 알고리즘과 같은 목표 지향 변형(§ 관련 문제 및 알고리즘 참조), 그래프 가지치기를 통해 최단 경로의 중간 세그먼트를 형성할 가능성이 있는 노드를 결정합니다(접근 기반 라우팅). 그리고 입력 그래프의 계층적 분해는 s-t 라우팅을 각각의 "transit 노드"에 연결하는 것으로 감소시키고 "highway"를 사용하여 이들 트랜짓 노드 사이의 최단 경로 계산을 수행합니다. 특정 문제에 대한 최적의 실제 수행을 위해서는 이러한 기술의 조합이 필요할 수 있습니다.^[24]

특화된 변종

아크 가중치가 작은 정수일 때($파라미터{\displaystyle }$C {\$displaystyle$C}로 경계지어짐),$$ 이 사실을 이용하는 특수화된 큐를 사용하여 Dijkstra의 알고리즘을 가속화할 수 있습니다. 이 유형의 첫 번째 알고리즘은 양의 정수 에지 가중치를 가진 그래프에 대한 Dial의 알고리즘(Dial 1969)으로 버킷 큐를 사용하여 실행 시간 $O{\displaystyle (E}$+ ${\displaystyle VC)}$ ${\displaystyle O(E$+ $VC)}$를 얻습니다$.$ Van Emde Boas 트리를 우선 순위 큐로 사용하면 $복잡성$이 O${\displaystyle (E}$ $log$⁡ 로그 ⁡ C) {\$display$ O(E \log \log C)}(Ahuja et al. 1990)로 이어집니다. 새로운 래딕스 힙과 잘 알려진 피보나치 힙의 조합을 기반으로 한 또 다른 흥미로운 변형은 $O{\displaystyle (\sqrt{E}}$+ V ${\displaystyle \sqrt{\mathrm{로그}}}$ ⁡ C) ${\displaystyle$O(E + V {\$sqrt {\$log C}}}(Ahuja et al. 1990)에서 실행됩니다. 마지막으로 이 특수한 경우에 가장 좋은 알고리즘은 다음과 같습니다. The algorithm given by (Thorup 2000) runs in ${\displaystyle O( E \log \log V )}$ time and the algorithm given by (Raman 1997) runs in ${\displaystyle O( E + V \min\{(\log V )^{1/3+\varepsilon },$$(\log$ C$)^{1/4+\varepsilon}\}}$ 시간$$.

관련 문제 및 알고리즘

다양한 수정을 통해 Dijkstra의 원래 알고리즘의 기능을 확장할 수 있습니다. 예를 들어, 때로는 수학적으로 최적이 아닌 솔루션을 제시하는 것이 바람직합니다. 최적이 아닌 솔루션의 순위 목록을 얻으려면 먼저 최적 솔루션을 계산합니다. 그래프에서 최적해에 나타나는 하나의 간선이 제거되고, 이 새로운 그래프에 대한 최적해가 계산됩니다. 원래 솔루션의 각 에지가 차례로 억제되고 새로운 최단 경로가 계산됩니다. 그런 다음 2차 솔루션의 순위가 매겨지고 첫 번째 최적 솔루션 다음에 제시됩니다.

Dijkstra의 알고리즘은 일반적으로 링크 상태 라우팅 프로토콜의 배후에 있는 작동 원리이며, OSPF와 IS-IS가 가장 일반적입니다.

Dijkstra의 알고리즘과 달리 Bellman-Ford 알고리즘은 그래프가 소스 정점에서 도달할 수 있는 음의 주기를 포함하지 않는 한 음의 에지 가중치가 있는 그래프에서 사용할 수 있습니다. 이러한 사이클이 존재한다는 것은 사이클이 통과할 때마다 총 중량이 낮아지기 때문에 최단 경로가 없다는 것을 의미합니다. 이 문장은 "경로"가 정점을 반복하도록 허용된다고 가정합니다. 그래프 이론에서는 일반적으로 허용되지 않습니다. 이론 컴퓨터 과학에서는 종종 허용됩니다.) Dijkstra의 알고리즘을 Bellman-Ford 알고리즘과 결합하여 음의 가중치 에지를 처리하는 것이 가능한데, 이러한 알고리즘을 Johnson의 알고리즘이라고 합니다.

A* 알고리즘은 표적에 대한 "거리"의 하한을 제공하는 추가 정보가 있는 경우 탐색해야 하는 서브그래프의 크기를 줄이는 Dijkstra 알고리즘의 일반화입니다.

데이크스트라의 알고리즘의 기초가 되는 과정은 프림의 알고리즘에서 사용되는 그리디 과정과 비슷합니다. Prim의 목적은 그래프의 모든 노드를 연결하는 최소 스패닝 트리를 찾는 것입니다. Dijkstra는 오직 두 개의 노드에만 관심이 있습니다. Prim's는 시작 노드에서 경로의 총 가중치를 평가하지 않고 개별 에지만 평가합니다.

너비 우선 검색은 가중치가 없는 그래프에서 Dijkstra 알고리즘의 특수한 경우로 볼 수 있으며, 여기서 우선 순위 대기열은 FIFO 대기열로 전락합니다.

빠른 행진 방법은 삼각형 메쉬 상에서 측지거리를 계산하는 Dijkstra의 알고리즘의 연속적인 버전으로 볼 수 있습니다.

동적 프로그래밍 관점

동적 프로그래밍 관점에서 Dijkstra의 알고리즘은 최단 경로 문제에 대한 동적 프로그래밍 함수식을 도달법(Reaching method)으로 푸는 연속 근사식입니다.^[25][26][27]

사실 알고리즘의 배후에 있는 논리에 대한 다이크스트라의 설명,^[28] 즉

문제 2. 주어진 두 노드 $P{\displaystyle }$ ${\displaystyle$ P$}$와 $Q{\displaystyle }$ ${\displaystyle Q}$ 사이의 최소 총 길이 경로를 찾습니다$.$

$우리$는$$R {\$displaystyle$ R$}$이$$P {\$displaystyle$P$$}에서$$Q {\$displaystyle$ Q$}$까지의 최소 경로에 있는 노드라면$$후자의 지식은 $P{\displaystyle }$ ${\displaystyle P}$에서 $R{\displaystyle }$ ${\displaystyle R}$까지의 최소 경로에 대한 지식을 의미한다는 사실을 사용합니다$.$

는 벨만의 유명한 최적의 원리를 최단 경로 문제의 맥락에서 비유한 것입니다.

참고 항목

• A* 검색 알고리즘
• 벨만-포드 알고리즘
• 유클리드 최단 경로
• Floyd-Warshall 알고리즘
• 존슨의 알고리즘
• 최장경로문제
• 병렬 전쌍 최단 경로 알고리즘

메모들

참고문헌

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 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. S2CID 6754003.
• 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. pp. 338–346. doi:10.1109/SFCS.1984.715934.
• Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
• Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks". Transportation Science. 32 (1): 65–73. doi:10.1287/trsc.32.1.65. S2CID 14986297.
• Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques – First Annual Report – 6 June 1956 – 1 July 1957 – A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
• Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3.
• Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (April 1990). "Faster Algorithms for the Shortest Path Problem" (PDF). Journal of the ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589.
• Raman, Rajeev (1997). "Recent results on the single-source shortest paths problem". SIGACT News. 28 (2): 81–87. doi:10.1145/261342.261352. S2CID 18031586.
• Thorup, Mikkel (2000). "On RAM priority Queues". SIAM Journal on Computing. 30 (1): 86–109. doi:10.1137/S0097539795288246. S2CID 5221089.
• Thorup, Mikkel (1999). "Undirected single-source shortest paths with positive integer weights in linear time". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.

외부 링크

• Minneapolis, University of Minnesota, Charles Babbage Institute, Edsger W. Dijkstra 구술 역사 인터뷰
• TDD를 이용한 Dijkstra 알고리즘 구현, Robert Cecil Martin, The Clean Code Blog