[Algorithm] 다익스트라 알고리즘
다익스트라 알고리즘이란
다익스트라 알고리즘은 그리디 알고리즘의 한 유형으로서,
특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다.
음의 값을 가지는 간선이 없을 때만 적용 가능하다.
다익스트라 알고리즘을 이해하기 위해서 먼저 힙 자료구조에 대해 알고있어야 한다.
힙 자료구조란
힙 자료구조는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조로서, 일종의 반정렬 상태를 유지한다. 반정렬 상태란, 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 상태를 의미하며, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(or 작은) 이진 트리에서 나타난다.
힙의 삽입
새로운 노드는 마지막 노드에 이어서 삽입된다. 새로운 노드가 삽입되면 부모 노드들과 교환하여 힙의 성질(반정렬 상태)을 만족시킨다.
힙의 삭제
힙의 삭제는 루트 노드를 삭제하는 것을 의미한다. 루트 노드를 삭제한 후 그 자리에 힙의 마지막 노드를 가져온다. 새로이 올라온 루트 노드는 자식 노드들과 교환하여 힙의 성질(반정렬 상태)을 만족시킨다.
다익스트라 알고리즘 구현
다익스트라 알고리즘은 다음과 같은 순서로 구현한다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다. 모든 노드에 대하여 최단 거리 판단이 완료되기 이전이니 무한대(1e9)로 초기화 한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 이 과정을 거치며 선택된 하나의 노드 (A)는 최단 거리 판단이 완료된다.
- 선택된 노드 (A)를 거쳐 다른 노드 (B)로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 이 때 다른 노드 (B)로 가는 비용을 계산하기 위한 시도는 노드 (B)를 방문한 것으로 간주하지 않는다.
- 위 과정에서 3 번 4 번 스텝을 반복한다.
다익스트라 알고리즘은 음의 간선이 없을 때만 적용 가능하다. 그 이유는 3번 스텝의 과정때문이다. 3번 스텝에서 가장 짧은 노드가 선택되었을 때 이후 이를 번복하는 과정이 없다. 만약 음의 간선이 있는 그래프라면 추후에 판단이 완료된 특정 노드까지의 최단거리가 더 짧아져 새로이 갱신이 필요하기 때문에 위 순서로 다익스트라 알고리즘을 구현하였을 때 오류가 발생한다.그렇기 때문에 다익스트라 알고리즘은 음의 간선이 없는 경우에만 이용할 수 있다.
구현 방법은 두가지가 있다.
- 구현하기 쉽지만 조금 느리게동작하는 코드
- 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
이 두가지 방법의 결정적인 차이는 위에 서술되어있는 5단계 중 3단계 과정, 즉 최단 거리가 가장 짧은 노드를 선택하는 과정을 선형적인 방법을 이용하여 선택하는 지, 우선순위 큐를 이용하여 선택하는 지의 차이이다.
구현하기 쉽지만 조금 느리게 동작하는 코드
1번부터 살펴보자. 아래 코드는 나동빈 님의 깃헙을 참고하였다.
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
bool visited[100001];
// 최단 거리 테이블 만들기
int d[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph[start].size(); j++) {
d[graph[start][j].first] = graph[start][j].second;
}
// 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph[now].size(); j++) {
int cost = d[now] + graph[now][j].second;
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph[now][j].first]) {
d[graph[now][j].first] = cost;
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill_n(d, 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}
위 코드에서, getSmallestNode() 의 시간복잡도는 O(n) 이다. 또한 dijkstra() 는 for 문 안에 getSmallestNode() 를 포함하기 때문에 O(n^2) = O(v^2) 의 시간 복잡도를 갖는다.
이 때 v 은 노드의 개수를 의미한다.
구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
이제 2번을 살펴보자. 아래 코드는 나동빈 님의 깃헙을 참고하였다.
#include <bits/stdc++.h>
#define INF 1e9 // 무한을 의미하는 값으로 10억을 설정
using namespace std;
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
vector<pair<int, int> > graph[100001];
// 최단 거리 테이블 만들기
int d[100001];
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({0, start});
d[start] = 0;
while (!pq.empty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
// cpp 의 priority_queue 는 키 값이 클수록 우선순위를 높게 쳐주는 최대 힙(Max Heap)을 이용한다
// 이러한 이유로 최소 힙이 필요한 경우에는 키 값에 음의 부호를 붙여 이용해야 한다
// 자주 사용하는 스킬이니 알아두면 좋다
int dist = -pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
// 현재 노드가 이미 처리된 적이 있다면 d[now] 값이 최솟값으로 확정된 경우이기 때문에
// d[now] < dist 는 항상 True 를 반환한다
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 갱신 발생
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].first));
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
}
// 최단 거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// 도달할 수 있는 경우 거리를 출력
else {
cout << d[i] << '\n';
}
}
}
위 코드에서 우선순위 큐에 노드를 넣었다가 빼는 작업은 최대 간선의 개수(E) 만큼 수행된다. 우선순위 큐에서 삽입과 삭제는 O(logN) 의 시간복잡도를 가지기 때문에, 위 다익스트라 알고리즘은 O(ElogE) 의 시간 복잡도를 갖는다.
간선의 개수(E)는 최대 N(N-1)/2 이기 때문에 O(logE) 는 O(logN^2) = O(logN) 이다.
즉 위 다익스트라 알고리즘은 O(ElogN) 의 시간복잡도를 갖는다.
2번의 코드가 1번의 코드보다 더 빠르게 동작한다고 한다. 시간복잡도 만을 비교하였을 때 1번은 O(v^2), 2번은 O(ElogE) 이다. 하지만, E 가 최대인 경우, 즉 v(v-1)/2 인 경우 O(ElogE) = O(v^2logv) 가 되며 2번이 1번보다 더 느리게 작동하는 것 처럼 보인다. 난 아직 이 문제에 대한 명확한 해답을 찾지 못하였다. 다음에 기회가 된다면 더 자세히 찾아보도록 하겠다.
Leave a comment