다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 방향/무방향 그래프에서 하나의 시작점에서 모든 정점까지의 최단 거리를 구해주는 알고리즘입니다.
주의할 사항은 방향/무방향 그래프에서 간선의 가중치가 양수여야만 합니다.
음수인 경우 시작점에서 거리가 가까운 정점을 구하고 탐색을 이어나가다가 음수 간선을 마주치면 거리가 줄어들 수 있어서 알고리즘이 불완전하게 됩니다.
다익스트라는 다이내믹 프로그래밍(Dynamic Programming)을 적용한 탐색 알고리즘이기도 합니다.
예를 들어 A에서 F까지 가는 최단 거리의 경로가 A → B → C → D → E → F 라고 합시다.
그럼 이 경로에 포함되어있는 모든 부분 경로는 최단 거리입니다.
A부터 E까지의 최단 거리 경로인 A → B → C → D → E 가 최단 이어야 A → B → C → D → E → F 가 최단 거리이겠죠.
다익스트라 알고리즘은 다음과 같습니다
1) 출발 노드를 설정한다
2) 출발 노드를 기준으로 갈 수 있는 각 노드까지의 비용을 저장한다
3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4) 해당 노드를 거쳐서 갈 수 있는 노드에 관해 최소 비용을 갱신한다.
5) 3~4번을 반복한다.
아래 그림으로 예시를 들어 다익스트라 알고리즘을 실행해보겠습니다.
초기 상태입니다.
위와 같이 방향 있는 그래프가 있고, distance 배열은 모두 무한대로 채워져 있습니다.
출발점인 1에서 1까지의 거리는 0이므로 distance[1]에 0을 넣어줍니다.
출발점인 1번 정점을 힙에 넣어줍니다.
힙에 넣을 때, { 0 , 출발 지점 }으로 넣어줍니다.
앞으로 힙에 넣을 { a , b } 쌍에서 a는 거리, b는 정점을 의미합니다.
그럼 힙에 { 0 , 1 } 이 들어가 있습니다.
힙에서 거리가 가장 작은 { 0 , 1 } 을 선택합니다.
distance[1]이 0이 맞는지 확인합니다.
distance[1]이 0이 아니라면 { 0 , 1 } 은 힙에서 그냥 제거해줍니다.
distance[1] == 0 이므로, 1번 정점에서 갈 수 있는 점에 대한 거리를 갱신해줍니다.
거리를 갱신할 때에는, (현재 정점까지의 거리 + 다음 정점까지의 거리)가 distance에 있는 거리 값보다 작으면 갱신해줍니다.
정점 1을 기준으로 1에서 2까지의 거리는 1 이므로 0 + 1 = 1
distance[2] = ∞ 이므로 1이 더 작으니 distance[1] = 1로 갱신해 줍니다.
힙에 { 1 , 2 } 를 넣어줍니다.
정점 1을 기준으로 1에서 3까지의 거리는 6 이므로 0 + 6 = 6
distance[3] = ∞ 이므로 6이 더 작으니 distance[3] = 6으로 갱신해 줍니다.
힙에 { 6 , 3 } 을 넣어줍니다
정점 1을 기준으로 1에서 5까지의 거리는 4 이므로 0 + 4 = 4
distance[5] = ∞ 이므로 4가 더 작으니 distance[5] = 4로 갱신해 줍니다.
힙에 { 4 , 5 } 를 넣어줍니다.
{ 0 , 1 } 로 할 수 있는 모든 갱신을 마쳤으니 힙에서 제거해줍니다.
힙에서 거리가 가장 작은 { 1 , 2 } 을 선택합니다.
distance[2]가 1이 맞는지 확인합니다.
distance[2] == 1 이므로, 2번 정점에서 갈 수 있는 점에 대한 거리를 갱신해줍니다.
정점 2을 기준으로 2에서 3까지의 거리는 2 이므로 1 + 2 = 3
distance[3] = 6 이였으므로 1이 더 작으니 distance[3] = 3으로 갱신해 줍니다.
힙에 { 3 , 3 } 을 넣어줍니다
정점 2을 기준으로 2에서 4까지의 거리는 8 이므로 1 + 8 = 9
distance[4] = ∞ 이므로 9가 더 작으니 distance[4] = 9로 갱신해 줍니다.
힙에 { 9 , 4 } 를 넣어줍니다.
{ 1 , 2 } 로 할 수 있는 모든 갱신을 마쳤으니 힙에서 제거해줍니다.
힙에서 거리가 가장 작은 { 3 , 3 } 을 선택합니다.
distance[3]이 3이 맞는지 확인합니다.
distance[3] == 3 이므로, 3번 정점에서 갈 수 있는 점에 대한 거리를 갱신해줍니다.
정점 3을 기준으로 3에서 4까지의 거리는 3 이므로 3 + 3 = 6
distance[4] = 9 이였으므로 6이 더 작으니 distance[4] = 6으로 갱신해 줍니다.
힙에 { 6 , 4 } 를 넣어줍니다
{ 3 , 3 } 로 할 수 있는 모든 갱신을 마쳤으니 힙에서 제거해줍니다.
힙에서 거리가 가장 작은 { 4 , 5 } 을 선택합니다.
distance[5]가 4가 맞는지 확인합니다.
distance[5] == 4 이므로, 5번 정점에서 갈 수 있는 점에 대한 거리를 갱신해줍니다.
5번 정점에서 갈 수 있는 정점은 없으므로 종료해줍니다.
{ 4 , 5 } 로 할 수 있는 모든 갱신을 마쳤으니 힙에서 제거해줍니다.
힙에서 거리가 가장 작은 { 6 , 3 } 을 선택합니다.
distance[3]이 6이 맞는지 확인합니다.
distance[3] == 3 이므로 힙에서 { 6 , 3 }을 그냥 제거해줍니다.
힙에서 거리가 가장 작은 { 9 , 4 } 을 선택합니다.
distance[4]이 9가 맞는지 확인합니다.
distance[4] == 6 이므로 힙에서 { 9 , 4 }을 그냥 제거해줍니다.
힙이 비었으므로 다익스트라 알고리즘을 종료해줍니다.
다익스트라의 구현
위 알고리즘으로 다익스트라를 구현할 수 있습니다.
1) 전체 그래프를 입력받고 초기화
2) 방문체크하는 배열, 비용을 저장하는 배열 총 2개 선언
3) 최소비용을 가지는 정점을 반환하는 함수 구현
이 방식으로 다익스트라를 구현하면 N개의 정점에 대해 최소 비용을 가지는 정점을 반환하는 함수는 N번 탐색하기 때문에 O(N^2)의 시간 복잡도를 가지게 됩니다.
이렇게 구현하면 정점은 많지만, 간선의 수가 적을 때 정점의 개수만큼 탐색하기 때문에 매우 비효율적입니다.
이를 개선한 방법이 힙을 통한 구현입니다.
이 힙을 사용한 다익스트라 알고리즘은 사전에 설명한 것과 같습니다.
C++에서는 힙을 사용하기 위한 자료구조가 priority_queue입니다.
다익스트라 알고리즘을 아래처럼 구현했습니다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 1e9+10;
vector<pii> adj[1002];
int dis[1002];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//n: 정점 개수, m: 간선 개수
int n, m;
cin >> n >> m;
//간선 정보 입력 받기
for(int i=0;i<m;i++) {
int from, to, cost;
cin >> from >> to >> cost;
adj[from].push_back({cost,to});
}
//시작점 끝나는점 입력
int start, end;
cin >> start >> end;
//dis배열 무한대로 초기화, 힙 선언
fill(dis, dis+n+1,INF);
priority_queue<pii, vector<pii>,greater<pii>> pq;
//다익스트라 알고리즘 시작
//시작 정점 거리 0
dis[start] = 0;
//힙에는 <거리, 정점> 으로 push
pq.push({dis[start],start});
//힙이 비어있을때까지 반복
while(!pq.empty()) {
auto cur = pq.top(); pq.pop();
int dist = cur.first;
int idx = cur.second;
if(dis[idx]!=dist) continue;
//현재 정점에서 갈 수 있는 모든 정점에 대해
for(auto next : adj[idx]) {
int cost = next.first;
int nidx = next.second;
if(dis[nidx] > dist + cost){
dis[nidx] = dist + cost;
pq.push({dis[nidx], nidx});
}
}
}
}
댓글