다익스트라
개념
다이나믹 프로그래밍을 활용한 최단 경로 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다.
구현
- 출발 노드 설정
- 출발 노드 기준으로 각 노드의 최소 비용 저장
- 방문하지 않은 노드 중 가장 비용이 적게 드는 노드 선택
- 선택한 노드를 거쳐 특정한 노드로 가는 경우를 고려해 최소 비용 갱신
- 3~4를 반복
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
// 선형 탐색 방법
// 시간복잡도: O(n^2)
#include <stdio.h>
int number = 6; // 정점의 개수
int INF = 1000000000; // 무한대 표현
// 전체 그래프 초기화
int a[6][6] = {
{0, 2, 5, 1, INF, INF},
{2, 0, 3, 2, INF, INF},
{5, 3, 0, 3, 1, 5},
{1, 2, 3, 0, 1, INF},
{INF, INF, 1, 1, 0, 2},
{INF, INF, 5, INF, 2, 0}
};
bool visited[6]; // 방문한 노드인지 여부 기록
int distance[6]; // 최단 거리(비용) 저장
// 가장 최소 거리를 가지는 정점 반환(방문하지 않았던 노드 중)
int getSmallIndex() {
int min = INF;
int index = 0;
for(int i=0;i<number;i++) {
// 방문하지 않았고, 현재 최솟값보다 더 작은 비용을 가지는 거리가 존재한다면,
// 최솟값 갱신
if(distance[i] < min && !visited[i]) {
min = distance[i];
index = i; // 최소 비용의 위치 기억
}
}
return index;
}
// 다익스트라 수행(특정 정점에서 다른 모든 정점으로 가는 최소비용 구하는 함수)
void dijkstra(int start) {
for(int i=0;i<number;i++) {
distance[i] = a[start][i]; // 시작점에서 출발했을 때, 모든 경로까지의 비용 담아줌
}
visited[start] = true; // 시작점 방문
for(int i=0;i<number-2;i++) { // 첫 노드, 마지막 노드 제외(-2)
int current = getSmallIndex(); // 현재 방문하지 않은 노드 중, 가장 비용이 적게드는 인덱스를 가져오고,
visited[current] = true; // 방문처리
// 그 노드에 인접한 모든 노드 확인
for(int j=0;j<number;j++) {
if(!visited[j]) {
if(distance[current] + a[current][j] < distance[j]) {
distance[j] = distance[current] + a[current][j];
}
}
}
}
}
int main(void) {
dijkstra(0);
for(int i=0;i<number;i++) {
printf("%d ", distance[i]);
}
}
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 우선순위 큐(heap구조)
// O(N * logN)
// pair 비교는 첫번째 -> 두 번째 순이다.. pair를<거리,노드>로 바꿔야할듯..?
#include <iostream>
#include <vector>
#include <queue> // 힙 구조를 사용하기 위함(우선순위 큐)
using namespace std;
int number = 6;
int INF = 1000000000;
vector<pair<int, int> > a[7]; // 간선 정보(pair 형태로 자신과 연결된 노드 정보 저장)
int d[7]; // 최소 비용
void dijkstra(int start) {
d[start] = 0; // 탐색 시작하는 노드의 최소비용은 0
priority_queue<pair<int, int> > pq; // 힙구조 유지
pq.push(make_pair(start, 0));
// 가까운 순서대로 처리 -> 큐 사용
while(!pq.empty()) { // 우선순위 큐가 비어있지 않다면
int current = pq.top().first; // 큐의 가장 위에는 가장 적은 비용을 가진 node의 정보가 들어있다.
// 짧은 것이 먼저 오도록 음수화
int distance = -pq.top().second;
pq.pop();
// 최단 거리가 아닌 경우 스킵
if(d[current] < distance) continue;
for(int i=0;i<a[current].size();i++) {
// 선택된 노드의 인접노드를 담아줌
int next = a[current][i].first;
// 선택된 노드를 거쳐서 인접노드로 가는 비용 계산
int nextDistance = distance + a[current][i].second;
// 기존의 비용과 비교
if(nextDistance < d[next]) {
d[next] = nextDistance;
pq.push(make_pair(next, -nextDistance));
}
}
}
}
int main(void) {
for(int i=1;i<=number;i++) {
d[i] = INF;
}
a[1].push_back(make_pair(2,2)); // 1번 노드에서 2번 노드로 가는 비용은 2
a[1].push_back(make_pair(3,5)); // 1번 노드에서 3번 노드로 가는 비용은 5
a[1].push_back(make_pair(4,1));
a[2].push_back(make_pair(1,2));
a[2].push_back(make_pair(3,3));
a[2].push_back(make_pair(4,2));
a[3].push_back(make_pair(1,5));
a[3].push_back(make_pair(2,3));
a[3].push_back(make_pair(4,3));
a[3].push_back(make_pair(5,1));
a[3].push_back(make_pair(6,5));
a[4].push_back(make_pair(1,1));
a[4].push_back(make_pair(2,2));
a[4].push_back(make_pair(3,3));
a[4].push_back(make_pair(5,1));
a[5].push_back(make_pair(3,1));
a[5].push_back(make_pair(4,1));
a[5].push_back(make_pair(6,2));
a[6].push_back(make_pair(3,5));
a[6].push_back(make_pair(5,2));
dijkstra(1);
for(int i=1;i<=number;i++) {
printf("%d ", d[i]);
}
}
참고: https://velog.io/@max9106/Algorithm-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra-Algorithm