데이크스트라 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
데이크스트라 알고리즘은 1956년 에츠허르 데이크스트라가 개발한 최단 경로 문제 해결 알고리즘이다. 이 알고리즘은 그래프 내의 특정 시작 노드에서 다른 모든 노드까지의 최단 거리를 계산하며, 1959년에 발표되어 그의 명성을 높이는 데 기여했다.
1956년, 에츠허르 데이크스트라는 네덜란드 국립 수학 정보과학 연구소(CWI)에서 새로운 컴퓨터 ARMAC의 성능을 시연하기 위한 문제로 최단 경로 문제를 고안했다.[36] 그는 암스테르담에서 로테르담까지의 최단 경로를 찾는 문제를 약 20분 만에 해결하는 알고리즘을 개발했다. 1959년에 발표된 이 알고리즘은[39][40] 그의 명성을 높이는 데 큰 기여를 했다. 그는 연필과 종이 없이 알고리즘을 설계함으로써 불필요한 복잡성을 피할 수 있었다고 회고했다.[32]
데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 성능을 입증하기 위해 최단 경로 알고리즘을 고안했다. 그는 이 알고리즘을 이용해 약간 단순화된 네덜란드 64개 도시의 교통 지도에서 최단 경로를 찾는 데 활용했다.[36][32]
데이크스트라 알고리즘의 정확성은 방문한 노드의 수에 대한 수학적 귀납법을 사용하여 증명할 수 있다.[17]
데이크스트라 알고리즘의 실행 시간은 그래프의 간선 수 (|E|)와 정점 수 (|V|)에 따라 달라진다.
알고리즘은 각 노드까지의 거리를 초기화하고, 방문하지 않은 노드 중에서 가장 가까운 노드를 선택하여 해당 노드에서 인접 노드까지의 거리를 갱신하는 방식으로 작동한다. 데이크스트라 알고리즘은 도시 지도에서 최단 경로를 찾는 문제에 비유될 수 있으며, 스마트폰의 지도 서비스 및 내비게이션 시스템의 핵심 기술로 활용된다.
데이크스트라 알고리즘은 우선순위 큐를 사용하여 실행 시간을 단축할 수 있으며, 정확성은 수학적 귀납법으로 증명된다. 실행 시간은 그래프의 간선 수와 정점 수에 따라 다르며, 다양한 자료 구조를 사용하여 효율성을 높일 수 있다. A* 알고리즘, 벨먼-포드 알고리즘, 너비 우선 탐색 등과 관련이 있으며, OSPF와 IS-IS와 같은 링크 상태 라우팅 프로토콜에도 적용된다. 또한, 간선 가중치가 작은 정수인 경우, 특수한 단조 우선순위 큐를 사용하여 속도를 향상시킬 수 있다.
2. 역사
Dijkstra영어는 또한 ARMAC의 하드웨어 엔지니어들이 제기한 전선 사용량 최소화 문제를 해결하기 위해 프림 알고리즘(최소 신장 트리 알고리즘)을 재발견했다.[37][38] 이 알고리즘은 이미 Vojtěch Jarník와 로버트 프림에 의해 발견되었지만, Dijkstra영어는 독자적으로 이를 재발견하고 발표했다.[39][40]
이 알고리즘은 OSPF 등의 인터넷 라우팅 프로토콜이나 내비게이션의 경로 탐색, 철도 경로 안내에도 이용되고 있다.
3. 알고리즘
데이크스트라 알고리즘은 시작점에서 목표 지점까지의 최단 경로를 찾기 위해 다음과 같은 단계를 거친다. 각 단계에서 '간선 완화'라는 과정을 통해 거리를 개선한다.
1. 모든 꼭짓점을 미방문 상태로 표시하고, 미방문 꼭짓점들의 집합을 만든다.
2. 모든 꼭짓점에 시험적 거리 값을 부여한다. 시작점은 0, 나머지는 무한대로 설정하고 시작점을 현재 위치로 한다.
3. 현재 꼭짓점에서 미방문 인접 꼭짓점까지의 거리를 계산하고, 더 작은 값으로 시험적 거리 값을 갱신한다.
4. 현재 꼭짓점에 인접한 모든 미방문 꼭짓점을 확인했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거한다.
5. 다음 단계를 진행한다.
3. 1. 설명
Dijkstra's algorithm영어은 어떤 변도 음수 값을 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 도시 지도에서 출발지와 목적지 사이의 최단 거리를 찾는 문제에 비유할 수 있다.[32] 각 교차로는 노드, 도로는 간선으로 표현되며, 각 교차로에는 출발지로부터의 거리가 표시된다.
알고리즘의 동작 과정은 다음과 같다.
# 모든 교차로의 거리를 무한대로 초기화하고, 시작 교차로의 거리를 0으로 설정한다.
# 현재 교차로에서 연결된 모든 미방문 이웃 교차로에 대해 거리를 갱신하고, 현재 교차로를 방문 처리한다. 이때 거리를 갱신하는 과정은 '간선 완화'라고 불리며, 현재 위치까지의 최단 거리에 도로 길이를 더한 값과 교차로에 쓰여 있는 값을 비교하여 더 작은 값으로 갱신하는 방식으로 이루어진다.
# 방문하지 않은 교차로 중 거리가 가장 작은 교차로를 새로운 현재 교차로로 선택하고, 위 과정을 반복한다.
# 목적지 교차로가 방문 처리되거나, 더 이상 방문할 교차로가 없으면 알고리즘을 종료한다.
이 알고리즘은 목적지뿐만 아니라 출발지에서 도달 가능한 모든 노드에 대한 최단 경로를 제공한다. 하지만, 모든 교차로를 고려하기 때문에 특정한 지도에서는 상대적으로 느리게 작동할 수 있다.
3. 2. 의사 코드
'''function''' Dijkstra(''Graph'', ''source''):
create vertex set Q
'''for each''' vertex ''v'' in ''Graph'': ''// 초기화''
dist[''v''] ← INFINITY ''// source에서 v까지의 아직 모르는 길이''
prev[''v''] ← UNDEFINED ''// source에서 최적 경로의 이전 꼭짓점''
add ''v'' to ''Q'' ''// 모든 노드는 초기에 Q에 속해있다 (미방문 집합)''
dist[''source''] ← 0 ''//'' ''source에서 source까지의 길이''
'''while''' ''Q'' is not empty:
''u'' ← vertex in ''Q'' with min dist[u] ''// 최소 거리를 갖는 꼭짓점''
''// 을 가장 먼저 선택한다''
remove ''u'' from ''Q''
'''for each''' neighbor ''v'' of ''u'': ''// v는 여전히 Q에 있다.''
''alt'' ← dist[''u''] + length(''u'', ''v'')
'''if''' ''alt'' < dist[''v'']: ''// v 까지의 더 짧은 경로를 찾았을 때''
dist[''v''] ← ''alt''
prev[''v''] ← ''u''
'''return''' dist[], prev[]
```
위 의사 코드에서
만약 `source`에서 `target`까지의 최단 경로만을 구하고 싶다면, `u` = `target` 일 때 검색을 종료할 수 있다.
`source`에서 `target`까지의 최단 경로는 역방향 반복을 통해 얻을 수 있다.
```
''S'' ← empty sequence
''u'' ← ''target''
'''while''' prev[''u''] is defined: ''// 스택 S로 최단 경로를 만든다''
insert ''u'' at the beginning of ''S'' ''// 꼭짓점을 스택에 넣는다''
''u'' ← prev[''u''] ''// target에서 source로 이동한다''
insert ''u'' at the beginning of ''S'' ''// source를 스택에 넣는다''
```
위 과정을 거치면 수열 `S`는 `source`에서 `target`으로 가는 경로에 있는 꼭짓점의 목록이거나 경로가 존재하지 않다면 빈 수열이 된다.
3. 3. 우선순위 큐 사용
Minimum priority queue영어는 `add_with_priority()`, `decrease_priority()`, `extract_min()`의 세 가지 기본 연산을 제공하는 추상 자료형이다. 이러한 자료구조를 사용하면 기본 큐를 사용하는 것보다 계산 시간을 단축시킬 수 있다. 특히, 피보나치 힙[34]이나 브로들 큐는 이 세 가지 연산에 대해 최적의 구현을 제공한다.[41]
의사 코드는 다음과 같다.
```
1 '''function''' Dijkstra(''Graph'', ''source''):
2 dist[''source''] ← 0 ''// 초기화''
3
4 create vertex set Q
5
6 '''for each''' vertex ''v'' in ''Graph'':
7 '''if''' ''v'' ≠ ''source''
8 dist[''v''] ← INFINITY ''// 소스에서 v까지의 아직 모르는 길이''
9 prev[''v''] ← UNDEFINED ''// v의 이전 노드''
10
11 ''Q''.add_with_priority(''v'', dist[''v''])
12
13
14 '''while''' ''Q'' is not empty: ''// 메인 루프''
15 ''u'' ← ''Q''.extract_min() ''// 최고의 꼭짓점을 제거하고 반환한다''
16 '''for each''' neighbor ''v'' of ''u'': ''// Q에 여전히 남아 있는 v에 대해서만''
17 ''alt'' ← dist[''u''] + length(''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
```
초기화 단계에서 우선순위 큐에 모든 꼭짓점을 채우는 대신, ''소스''만을 포함하도록 초기화할 수도 있다. 그러면, 블록에서 꼭짓점이 큐에 없다면 꼭짓점을 큐에 삽입해야 한다.[34]
C++에서는 g++ 확장인 __gnu_pbds::priority_queue는 기본적으로 페어링 힙을 사용하므로[30], 이를 사용하면 피보나치 힙과 동등한 계산량의 코드를 쉽게 구현할 수 있다.
4. 정확성의 증명
'''불변 가설:''' 각 방문 노드 v|v영어에 대해, `dist[v]`는 시작점에서 v|v영어까지의 최단 거리이며, 각 미방문 노드 u|u영어에 대해, `dist[u]`는 방문 노드를 통해서만 이동할 때 시작점에서 u|u영어까지의 최단 거리이며, 그러한 경로가 없으면 무한대이다. (참고: `dist[u]`가 미방문 노드에 대한 실제 최단 거리라고 가정하지 않지만, `dist[v]`는 실제 최단 거리이다.)
시작점에서 노드로 갈 수 있는 경로가 있는 경우, 방문한 노드 v|v영어에 대해 `거리[v]`는 시작점부터 v|v영어까지 가장 짧은 거리이고, 방문하지 않은 노드 u|u영어에 대해 `거리[u]`는 시작점부터 u|u영어까지 가장 짧을 것으로 추정되는 거리이다. 시작점에서 노드로 갈 수 없는 경우가 없다면 노드까지의 거리는 무한대로 둔다.
그래프에 시작점만 있는 경우, 위의 가설은 자명하며, 수학적 귀납법의 기저 사례로 사용된다.
그렇지 않으면, 이 가정이 방문한 꼭짓점이 ''n-1''일 때 성립한다고 가정하자. 이 경우에, 모든 미방문 꼭짓점에서 `dist[u]`가 가장 작은 u|u영어에 대해서 `1=dist[u] = dist[v] + length[v,u]`을 만족하는 변 vu|vu영어를 선택한다. `dist[u]`는 시작점에서 u|u영어까지의 가장 짧은 거리로 볼 수 있다. 만약 그 경로보다 더 짧은 경로가 있고, 그 경로의 첫 번째 미방문 꼭짓점을 w|w영어라고 한다면 처음의 가정인 `dist[w]` > `dist[u]`에 의해서 모순이 생긴다. 이와 비슷하게, u|u영어로 가는 경로 중 미방문 꼭짓점을 지나지 않는 더 짧은 경로가 있고, 그 경로의 마지막 꼭짓점이 w|w영어라고 한다면, `1=dist[u] = dist[w] + length[w,u]`이여야 하기 때문에 여전히 모순이 생긴다.
u|u영어를 처리하고 나서도 각각의 미방문 꼭짓점 w|w영어에 대해서, `dist[w]`는 여전히 방문한 꼭짓점만을 통해서 시작점에서 w|w영어로까지의 최단 거리이다. 그 이유는 u|u영어를 통과하지 않는 경로 중 더 짧은 경로가 있다고 한다면 이미 찾았었을 것이며, u|u영어를 통하는 경로가 더 짧다면 u|u영어를 처리할 때 갱신되었을 것이기 때문이다.
5. 실행 시간
이진 힙을 사용할 때 평균 시간 복잡도는 최악의 경우보다 더 낮다. 변의 비용이 일반적인 확률 분포와 무관하다고 가정하면, ''decrease-key'' 연산의 기대 연산 횟수의 상한은 이므로, 총 수행 시간은 다음과 같다.[42]
: