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

📌 Intro

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로를 찾기 위한 알고리즘은 여러 종류가 있는데 그 중에서 가장 많이 사용되는 다익스트라 알고리즘에 대해 알아보도록 하자.

📌 Dijkstra Algorithm

다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는데 주로 사용한다. 즉 한 지점으로부터 다른 모든 지점까지 각각의 최단경로를 구할 수 있게 되는 것이다.
다익스트라 알고리즘을 사용하기 위해서는 모든 간선의 가중치가 음이 아니어야 한다는 조건이 있다.
다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류되는데, 매번 "가장 비용이 적은 노드"를 선택하기 때문이다. 알고리즘에 대해 간략하게 정리하면 다음과 같다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3, 4 과정을 반복한다.

STEP 0

그럼 예시를 통해 더 자세히 알아보도록 하자. 다음과 같은 그래프가 주어졌다고 가정해보자.

출발 노드를 1로 설정했다고 가정하고 1번 노드에서 다른 모든 노드로의 최단 거리를 계산하는 과정을 살펴볼 것이다. 먼저 초기 상태는 다른 모든 노드로 가는 최단 거리를 무한대로 초기화한다. 그리고 1번 노드에서 1번 노드로 가는 길은 없기 때문에 0으로 초기화 한다. 그러면 초기화 된 거리 리스트는 다음과 같을 것이다.

 

STEP 1

출발 노드를 1로 설정했기 때문에 1번 노드와 연결된 모든 간선을 하나씩 확인하면 된다. 1번 노드는 2, 4, 5번 노드와 연결되어 있고, 각각의 노드로 이동하는 비용을 계산해보면 다음과 같다.
1 → 2 : 2
1 → 3 : 무한
1 → 4 : 1
1 → 5 : 3
그렇다면 그래프와 거리 리스트는 다음과 같을 것이다. 이 때 현재 처리중인 노드와 간선은 하늘색으로, 방문한 노드는 회색으로, 이미 처리한 간선은 점선으로 표현했다.

 

 

STEP 2

두 번째 단계에서는 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. 따라서 거리가 1인 4번 노드를 선택하게 된다.
이후 4번 노드를 거쳐서 갈 수 있는 다른 노드는 없기 때문에 다른일은 일어나지 않게 된다.

 

 

STEP 3

세 번째 단계에서도 역시 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. 따라서 거리가 2인 2번 노드를 선택하게 된다.
이후 2번 노드를 거쳐서 갈 수 있는 다른 노드로는 3, 5번이 있고, 각각의 노드로 이동하는 비용을 계산해보면 다음과 같다.
1 → 2 → 3 : 2 + 5
1 → 2 → 5 : 2 + 7

 

현재 상태를 살펴보면 1번 노드에서 출발해서 2번 노드를 거친 후 3번 노드, 5번 노드로 이동하는 것에 대해서 확인하기 때문에 1 → 2로 이동한 거리에 2 → 3으로 이동한 거리를 더해주어야 한다.
현재 거리 리스트에 저장된 3번 노드까지의 거리는 무한대이고, 1 → 2 → 3순으로 이동했을 때의 거리는 7이기 때문에 거리 리스트를 수정해주도록 한다.
거리 리스트에 저장된 5번 노드까지의 거리는 3이지만 1 → 2 → 5순으로 이동했을 때의 거리는 9이기 때문에 거리 리스트를 수정해주지 않는다.

 

 

STEP 4

마찬가지로 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. 따라서 거리가 3인 5번 노드를 선택하게 된다.
이후 5번 노드를 거쳐 갈 수 있는 다른 노드는 3번이 있고, 이동하는 비용을 계산해보면 다음과 같다.
1 → 5 → 3 : 3 + 3

 

거리 리스트에 저장되어 있는 3번 노드까지의 거리는 7이었지만 1 → 5 → 3순서로 이동한 거리 비용은 6이 된다. 따라서 거리 리스트를 수정해주도록 한다.

 

 

STEP 5

마지막으로 방문하지 않은 노드는 3번 노드이기 때문에 3번 노드를 선택한다.
3번 노드로부터 이동할 수 있는 다른 노드는 없기 때문에 다른 일은 일어나지 않고 종료된다.
이 때 사용하지 않은 간선이 2개 있다. 하지만 두 간선을 이용해서 이동할 경우 방문한 노드를 재방문하는 것과 같기 때문에 해당 간선을 확인하지 않고 종료한다.

 

📌 Details

다익스트라 알고리즘은 "방문하지 않은 노드 중 가장 최단 거리가 짧은 노드를 선택하는 과정"의 반복이다. 이 때 선택된 노드는 "최단 거리"가 완전히 선택된 노드이므로 알고리즘이 반복되어도 최단 거리가 줄어들지 않는다. 즉, 한 단계당 하나의 노드에 대한 최단 거리를 확실하게 찾는 것이다.

 

다익스트라를 구현하는 방법으로는 크게 두 가지가 있는데 속도가 조금 느리지만 간단하게 구현하는 방법(1)과 속도가 빠르지만 구현하기 조금 까다로운 방법(2)이 있다. 두 방법의 차이는 비용이 최소인 간선을 찾는 방법이다.

(1) 방법은 반복문을 이용하여 비용이 최소인 간선을 찾기 때문에 시간 복잡도가 O(V² + E) 이다.

(2) 방법은 간선 한 개당 한 개의 원소가 우선순위 큐에 추가될 수 있기 때문에 시간 복잡도가 O(ElogE)이다. 다른 곳에서 시간 복잡도가 O(ElogV) 라고 하는 곳도 있을텐데 O(ElogE)나 O(ElogV)나 Big-O 관점에서 보면 동일하다.
(E : 간선, V : 노드)

📌구현(C ++)

#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';
        }
    }
}

C++ 에서 priority_queue는 가장 큰 값이 TOP을 유지하도록 되어있다. 하지만 다익스트라 알고리즘에서는 priority_queue의 TOP에 가장 작은 간선의 가중치가 있어야 하기 때문에 음으로 바꾸어 넣어주는 것이다. 물론 priority_queue를 가장 작은 값이 TOP으로 오도록 만들 수 있다.

 

또, priority_queue는 원소로 pair가 들어갔을 때 기본적으로 앞의 원소를 기준으로 정렬한다. 이 때문에 priority_queue에 원소를 push해줄 때 <경로의 비용, 노드 번호> 순으로 넣어주는 것이다.

📌 관련 문제

다익스트라 알고리즘을 사용해서 풀 수 있는 문제는 많지만 직접 풀어보면서 다익스트라 알고리즘에 익숙해졌던 문제들은 다음과 같다. 

 

1916번: 최소비용 구하기

1753번: 최단경로

이외에도 백준에서 알고리즘 분류로 들어가 "데이크스트라"를 선택하면 다양한 문제들을 만나볼 수 있다.

 

 

📌 경로 복원 방법

다익스트라 알고리즘을 이용하여 한 노드에서 다른 모든 노드까지의 최단 경로의 가중치를 찾을 수 있다. 그러면 그 가중치를 찾기 위해 이동하는 경로는 어떻게 해야할까?
최단 거리를 저장하는 배열을 만들어둔 것처럼 현재 노드로 이동하기 위해 이전에 거친 노드를 저장해두는 배열을 만들어 관리해주면 된다. 이 배열을 pre 배열이라고 하겠다. 그리고 그림예시를 통해 이해해보도록 하자.

시작 노드인 1번 노드를 통해 이동할 수 있는 노드는 2, 4, 5번 노드다. 최단 거리 배열을 수정해주고 pre테이블에 2, 4, 5번 노드는 1번 노드를 통해 이동했으므로 기록해둔다. 

 

간선의 가중치가 가장 낮은 간선은 1번 노드에서 4번 노드로 이동하는 간선이다. 4번 노드로 이동하더라도 다른 노드로 이동할 수 없기 때문에 최단 거리 배열이나 pre 테이블은 갱신되지 않는다. 

 

다음으로 가중치가 낮은 간선은 1번 노드에서 2번 노드로 이동하는 간선이다. 2번 노드로 이동하면 3번 노드와 5번 노드로 이동할 수 있다. 5번 노드로 이동하는 방법은 2번 노드를 거치는 방법보다 1번 노드에서 바로 5번 노드로 이동하는 것이 가중치가 더 작기 때문에 최단 거리 배열과 pre 테이블 모두 갱신되지 않는다.
하지만 3번 노드로 이동하는 경우 최단 거리 배열에 저장된 가중치보다 2번 노드를 거쳐 이동하는 간선의 가중치가 더 작기 때문에 갱신해주고 pre 테이블 역시 2번 노드를 거쳐서 왔으므로 갱신해준다. 

 

다음으로 간선의 가중치가 작은 간선은 1번에서 5번 노드로 이동하는 간선이다. 5번 노드에서 이동할 수 있는 노드는 3번이고 5번 노드를 거쳐 이동하는 거리가 최단 거리 배열에 저장되어 있는 가중치보다 작기 때문에 갱신해준다.
최단 거리 배열이 갱신되었기 때문에 3번 노드로 이동하기 위해 거치는 5번 노드로 pre 테이블을 갱신해준다. 

 

모든 노드를 방문하고나면 최단 거리 테이블과 pre 테이블에 결과가 저장된다. 3번 노드로 이동하기 위한 최단 거리는 6이고 이 때의 경로는 pre 테이블을 따라 올라가며 확인하면 된다.
3 → 5 → 1 (pre[3] -> pre[5] -> pre[1]) 이 된다. 

 

 

📌 경로 복원 방법 구현

#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];

// pre 테이블
int pre[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));
                pre[graph[now][i].first] = now;
            }
        }
    }
}

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';
        }
    }

    // 모든 노드로 가기 위한 최단 경로를 출력
    for (int i = 1; i <= n; i++) {
        int location = i;

        while (location) {
            cout << location << ' ';
            location = pre[location];
        }
        cout << '\n';
    }
}

pre 테이블을 통해 현재 노드로 오기 위한 이전 노드를 저장함으로써 경로를 복원할 수 있다. 이 때 출력하는 경로는 도착 지점으로부터 출발 지점이기(역순) 때문에 방향을 바꾸기 위해서는 약간의 처리를 해주면 된다.

 

 

참고

[1] 이것이 취업을 위한 코딩테스트다 with 파이썬