다익스트라 알고리즘
-
한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘(SSP 알고리즘)
-
최단거리를 구하는 알고리즘은 이 알고리즘과, 밸만포드 알고리즘, 플로이드 와샬 알고리즘이 있다.
-
최소 우선순위 큐를 이용해서 하나의 정점으로부터 인접한 간선들을 확장해 나가는 방식
-
프림알고리즘과 동작은 유사하지만 프림은 가중치와 정점의 key 값을 비교하여 key 값을 업데이트 할지 말지를 결정하고
-
다익스트라는 (Relaxation:)Relax는 key값이 없고, 최단 경로 추정 값(d[v])을 이용하여 d[v]를 업데이트 할지 말지를 결정했다.
그리고 Relax는 정점의 key값이 딱 주어진 것이 아니라 최단 경로 추정 값들이 누적되어온 결과
-
그래프의 가중치는 음수가 아니여야한다.
구현
-
모든 정점을 최소 우선순위 큐에 삽입한다.
-
최단 경로 가중치 값( d[v] )이 가장 작은 정점을 선택하여 인접 간선들에 대해 Relax를 수행하여, 시작 정점으로부터 각 정점까지의 최단 경로 비용을 계산한다.
시작점은 0,나머지는 무한대의 값으로 초기화하고
우선순위 큐에서 가장 d[v]최소값을 가진 정점을 꺼내어 릴렉스를 수행해준다.
-
두 연결된 간선 중에 선택 순서는 구현에 달려있으며 v2 먼저라고 하면,
d[v1] = 0 , d[v2] = ∞ , (v1,v2) = 6이므로 Relax 결과 d[v2] = 6으로 업데이트 된다.
v4도 마찬가지로 d[v4]=8이 된다.
-
v[1]의 인접 간선들을 다 업데이트했으므로, 최소 우선순위 큐에서 가장 작은 정점을 추출해 탐색을 시작한다.
d[v2]가 relax가 수행되어
d[v3]= 11,d[v5]=7로 업데이트가 되고
d[v2]=6, d[v4]=8 ,(v2,v4)=8이므로 relax 결과 d[v2]+(v2,v4) =14 > d[4] 이므로 업데이트 하지않고 넘어간다.
-
같은 과정을 반복하면
…
마지막으로 아래와 같은 결론이 남을 알 수 있다.
단점
- 음의 가중치 사용을 할 수 없다.
- 이유
- 이유는 이전 노드까지 계산해둔 최소거리 값이 최소라고 보장할 수 없기 때문이다.
- 다익스트라는 정점을 지날수록 가중치가 증가한다라는 사실을 전제하고 쓰여진 알고리즘이다.
- 하지만 음의 가중치가 있다면 정점을 지날수록 가중치가 감소할 수도 있다는 의미가 되므로 앞선 전제가 무너진다.
시간복잡도
우선순위 큐를 사용하는지 안하는지에 따라 시간복잡도는 다르다.
일반 큐를 사용한다면 중복갱신 횟수가 우선순위 큐에 비해 많아진다.
최종적으로 일반 큐에서는 O(E+V^2)에서 우선순위 큐 사용 시 O(ElogV) 의 시간복잡도를 가지게 되어
우선순위 큐 사용이 훨씬 빠름을 알 수 있다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <limits.h>
#define MAX_NODE 10001
using namespace std;
typedef pair<int, int> pii;
vector<pii> vc[MAX_NODE];
vector<int> dist;//최단거리
int V,E;
void dijkstra(int start)
{
dist[start]=0;
// 우선 순위 큐(최소 힙)
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push(pii(0,start));
while (!pq.empty())
{
int here = pq.top().second; //정점
int hereCost = pq.top().first; //가중치
pq.pop();
// 다음 정점을 우선순위 큐에 넣어준다.
for (int i = 0; i < vc[here].size(); i++)
{
int there = vc[here][i].first;
int thereCost = vc[here][i].second;
if(dist[here]+thereCost < dist[there]){
dist[there]=dist[here]+thereCost;
pq.push(pii(thereCost, there));
}
}
}
}
int main(){
scanf("%d %d", &V, &E);
dist.resize(V,0);
for(int i=0; i < V ; i++){
dist[i]=INT_MAX;
}
for (int i = 0; i < E; i++)
{
int from, to, val;
scanf("%d %d %d", &from, &to, &val);
vc[from].push_back(pii(to, val));
}
dijkstra(0);
for(int i=0;i<V;i++){
printf("%d : %d \n",i,dist[i]);
}
return 0;
}
/*
5 10
0 1 6
0 3 8
1 2 5
1 3 8
1 4 1
2 1 4
3 2 3
3 4 9
4 2 7
4 0 2
*/
참고
https://www.crocus.co.kr/683 [Crocus]
https://goodgid.github.io/Union-Find-Algorithm