[이취코] ch09-2. 최단 경로 / 다익스트라 알고리즘 (힙 이용)
앞에서 리스트로 순차 탐색해 다익스트림을 구현하는 방법을 알아보았다
하지만 그렇게 구현하는 것보다 더 효율적으로 다익스트림 알고리즘을 구현할 수 있는 방법이있다
바로 힙 자료구조를 이용하는 것이다
힙(heap) 자료구조
힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나다
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다
스택, 큐, 우선순위 큐를 비교하면
| 자료구조 | 추출되는 데이터 |
| 스택 (Stack) | 가장 나중에 삽입된 데이터 |
| 큐 (Queue) | 가장 먼저 삽입된 데이터 |
| 우선순위 큐 (Priority Queue) | 가장 우선순위가 높은 데이터 |
우선순위 큐는 c++에서 라이브러리를 제공하므로, 라이브러리를 그대로 사용하면 된다
단, c++에서는 최대 힙을 기준으로 우선순위가 구현되어있다 (즉, 숫자가 클 수록 우선순위가 높다는 것)
(자바는 최소 힙 기준)
언어마다 제공하는 라이브러리의 우선순위 기준이 다르므로, 필요한 우선순위에 맞게 구현해야한다
우선순위 큐를 이용해도 다익스트림 알고리즘을 구현하는 원리는 동일하다
최단거리를 저장하기 위한 1차원 리스트는 동일하게 사용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 생각하면 된다
아까와 같이 이 그래프가 있다고 생각하고, 시작노드는 1이다
[초기상태]
- 다른 모든 노드로 가는 최단거리를 '무한'으로 초기화
[step 0]
- 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발노드를 선택
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
여기까지는 앞과 똑같다. 이제 우선순위 큐에다가 거리와 노드 번호를 추가해준다
| 우선순위 큐 | (거리: 0, 노드: 1) |
다음, 큐에서 그냥 우선순위가 가장 높은(거리가 최솟값인) 데이터를 꺼내주기만 하면된다
[step 1]
- 1번 노드를 거쳐 다른 노드로 가는 비용 생각
- 갈 수 있는 노드 2, 3, 4
> 노드 2 : 0+2 = 2 (초기 상태 + 노드1에서 노드2까지 가는 비용)
> 노드 3 : 0+5 = 5 (초기 상태 + 노드1에서 노드3까지 가는 비용)
> 노드 4 : 0+1 = 1 (초기 상태 + 노드1에서 노드4까지 가는 비용)
- 테이블 초기화
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
* 노란 숫자는 이미 방문한 숫자이다
마찬가지로 우선순위 큐에 추가해준다
| 우선순위 큐 | (거리: 1, 노드: 4) (거리: 2, 노드: 2) (거리: 5, 노드: 3) |
또 마찬가지로 거리가 가장 작은 데이터를 꺼내준다 (거리: 1, 노드: 4)
이 때 꺼낸 노드가 이미 방문처리 된 노드라면 그냥 무시하고, 방문처리가 되지 않은 노드만 다루면 된다
[step 2]
- 노드 4에서 갈 수 있는 노드 3, 5 (노드 4까지 오는데 발생한 비용 + 새로 가는데 발생하는 비용)
> 노드 3 : 1 + 3 = 4
> 노드 5 : 1 + 1 = 2
- 테이블 초기화
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
* 노드 3의 거리는 원래 5였으나 4가 더 작으므로 갱신해준다
우선순위 큐에 추가해준다
| 우선순위 큐 | (거리: 2, 노드: 2) (거리: 2, 노드: 5) (거리: 4, 노드: 3) (거리: 5, 노드: 3) |
거리가 가장 작은 데이터를 꺼내준다 (거리: 2, 노드: 2)
이렇게 반복하면 마지막에는 (거리: 5, 노드: 3)이 남는데, 노드3은 이미 앞에서 방문처리 되었을 것이므로 무시한다
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
구현
#include <iostream>
#include <vector>
#include <queue>
#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()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
int dist = -pq.top().first; // 현재 노드까지의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
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';
}
}
}
int dist = -pq.top().first;
여기서 pq앞에 - 가 붙는 이유는 c++에서 우선순위 큐 라이브러리를 쓸 때 기본적으로 최대 힙이 기준이기 때문이다
즉, 값이 클수록 우선순위가 높다는 것이다
하지만 우리는 거리가 작을수록 (값이 작을수록) 우선순위가 높아야하므로 부호를 반대로 바꾸어 정렬해야한다
시간복잡도
여기서 시간복잡도는 O(ElogV) 이다 (E=간선의 개수, V=노드의 개수)
cf) 힙에 N개의 데이터를 넣고 이후에 모든 빼는 과정의 시간복잡도는 O(NlogN)