다익스트라 알고리즘

이번에는 최단 경로 알고리즘 하면 떠오르는 알고리즘 중 하나인 다익스트라 알고리즘에 대해서 정리해보자.

다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘의 정의부터 보자.

하나의 정점에서 출발해서 다른 노드들로 가는 각각의 최단 경로를 모두 구해주는 알고리즘이다.

용어로는 '단일 출발 최단 경로' 라고도 한다.

또, '단일 도착 최단 경로' 도 뒤집으면 똑같은 말이기도 하다.

모든 정점에서 출발해서 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 뒤집어서 생각하면 다익스트라와 똑같기 때문이다.

 

다만, 음의 간선에서는 사용할 수 없다. 이 때는 벨만-포드 알고리즘을 사용해야 한다. (아직 안 배웠다..)

 

사실 다익스트라 알고리즘 단계별 그림은 다른 블로그들의 설명도 너무 좋아서 핵심만 요약하는게 좋을 것 같다고 생각한다.

다익스트라 step

가장 먼저 출발 노드를 설정하기.

최단 거리 테이블을 무한대로 초기화 하기 (여기서 말하는 무한대는 아직 가보지 않은 곳을 무한대라고 표기한다.)

#1 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

#2 해당 노드를 거쳐서 다른 노드로 가는 비용을 계산한 후 최단 거리 테이블을 갱신한다.

#1과 #2를 반복하면서 최단 거리를 갱신해 나간다.

 

중요한 건 한 단계마다 하나의 노드에 대한 최단 거리를 찾게 된다는 점이다.

다익스트라 구현

구현 방법으로는 2차원 배열을 이용한 방법과 인접 리스트와 우선순위 큐를 이용한 방법이 있다.

2차원 배열로 구현을 하면 시간 복잡도가 O(V^2)이고, 인접 리스트와 우선순위 큐로 구현을 하면 O(ElogV)로 더 빠르게 가능하다.

 

우선순위 큐의 등장은 힙의 자료구조를 사용하는 개념 때문에 도입됐다.

#1에서 방문하지 않는 노드 중에서 최단 거리가 가장 짧은 노드를 선택할 때 모든 노드를 탐색하면 O(V)이지만, 최소 힙을 통해 찾게 된다면 O(logV)만에 찾을 수 있기 때문이다.

 

보통 코딩 테스트에서는 개선된 다익스트라 알고리즘으로 구현하는 것이 높은 성공률을 보여주기 때문에, 우선순위 큐를 이용한 구현 방법을 살펴보자.

 

이것도 중요할 수 있다. 우선순위 큐에 들어가거나 나오는 요소는 어떤 의미를 가질까?

요소는 {비용, 노드} 로 되어있는데, 이를 뜻하는 바는 노드까지 가는 최단 거리가 비용이라는 의미다.

 

또!

우선순위 큐를 기반으로 구현하게 되면, '서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 도 있다' 라는 것도 해결할 수 있게 된다.

 

코드의 주석까지 자세하게 달아놨다. 미래의 내가 까먹더라도 어떤 의미인지 빠르게 찾기 위해서..

반복 숙달하자!

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, start;
vector<pair<int, int> > adj[100001];
int dist[100001];

void dijkstra(int start) {
    priority_queue<pair<int, int> > pq; // default : max-heap
    pq.push({0, start}); // {비용, 노드}
    dist[start] = 0;
    while(!pq.empty()) {
        int cost = -pq.top().first; // 앞에 -를 붙이면 min-heap 으로 가능하다. (테크닉)
        int now = pq.top().second;
        pq.pop();
        
        // 중요: 앞서 말했듯이 우선순위 큐에서 요소를 뽑았을 때 그 의미는 다음과 같다.
        // now 노드까지 가는 최단 거리가 cost야.
        // 그런데 이미 더 적은 최단 거리로 갱신이 됬다면? 이 노드는 이미 처리가 됬다는 뜻이다.
        if(dist[now] < cost) continue;
        
        // 현재 노드와 연결된 다른 인접한 노드들을 확인한다.
        // 혹여나 현재 노드를 거쳐서 다른 노드의 거리를 갱신할 수 있으니까 확인해보는 것
        for(int i = 0; i < adj[now].size(); i++) {
            int next = adj[now][i].first;
            int nextCost = cost + adj[now][i].second;
            // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 갱신해준다.
            // 현재 노드까지의 최단거리 + 다른 노드의 거리 < 테이블[다른 노드] 최단 거리
            if(nextCost < dist[next]) {
                dist[next] = nextCost;
                pq.push({-nextCost, next}); // 마찬가지로 넣을 때 비용은 앞에 -붙여서 넣으면 min-heap구동
            }
        }
    }
}

int main() {
    cin >> n >> m >> start;
    
    // 모든 간선 정보를 입력받기
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // a 노드에서 b 노드로 가는 비용이 c 라는 의미
        adj[a].push_back({b,c});
    }
    
    // 문제에 따라 다르겠지만 보통은 나올 수 없는 값으로 무한대를 초기화 시켜준다.
    fill(dist, dist + 100001, 987654321);
    
    // 다익스트라 알고리즘 수행
    dijkstra(start);
    
    // 거리 테이블 출력
    for(int i = 1; i <= n; i++) {
        if(dist[i] == 987654321)
            cout << "INF\n";
        else
            cout << dist[i] << '\n';
    }
    
    return 0;
}

연습 문제들

확실히 어려운 개념이다 보니 랭크도 다르다..

최단경로

파티

녹색 옷 입은 애가 젤다지?

거의 최단경로

도로포장

해킹

도로검문

특정한 최단경로

KCM Travel

지름길

최소비용 구하기

택배 배송

간선 이어가기 2

백도어