[BOJ / C++] 최단경로 (골드4 - 다익스트라)

문제링크: https://www.acmicpc.net/problem/1753

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = (INT_MAX / 2) - 1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int v, e, st;
    cin >> v >> e;
    cin >> st;

    // {거리, 정점번호}
    vector<vector<pair<int, int>>> adj(v+1);
    vector<int> d(v+1, INF);

    for (int i = 0; i < e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    d[st] = 0;
    pq.push({d[st], st});

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        
        int curCost, curIdx;
        tie(curCost, curIdx) = cur;

        if (d[curIdx] != curCost) continue;
        
        for (auto nxt : adj[curIdx]) {
            int nxtCost, nxtIdx;
            tie(nxtCost, nxtIdx) = nxt;
            
            if (d[curIdx] + nxtCost < d[nxtIdx]) {
                d[nxtIdx] = d[curIdx] + nxtCost;
                pq.push({d[nxtIdx], nxtIdx});
            }
        }
    }

    for (int i = 1; i <= v; i++) {
        if (d[i] == INF) cout << "INF\n";
        else cout << d[i] << '\n';
    }
}

 

 

2. 시간복잡도

다익스트라 알고리즘의 시간복잡도는 현재 노드의 간선을 통해 갈 수 있는 다음 노드 (`adj[curIdx]`) 마다 해당 간선을 통해 더 짧은 경로로 갈 수 있는지 확인하고(O(E)), 더 짧은 경로가 되면 d테이블(최단경로 테이블) 갱신 후 우선순위 큐에 삽입하는 행위(O(logE))에 걸려서 O(ElogE)가 된다. 

 

문제에서 E는 3*10^5 이므로 ElogE < 10^9 이어서 시간제한 내에 통과 가능하다.

 

 

3. 분석

 

가장 기본적인 다익스트라 문제이다. 다익스트라 문제를 풀기 위해서는 (1) 최단경로 테이블 (d 테이블)과 (2) 우선순위 큐가 필요하다. 최단경로 테이블은 우선 INF로 초기화한다. 이후 시작점의 거리를 0으로 해준다. 우선순위 큐에도 {거리, 시작인덱스}를 삽입한다. {거리, 인덱스} 형태로 우선순위 큐에 삽입하는 이유는 우선순위큐에서 거리가 작은 순으로 추출하기 위해서이다.

 

우선순위 큐에서 가장 작은 값을 꺼내고 만약 curCost가 d[curIdx]와 다르다면 d[curIdx]는 최단거리이므로 우선순위 큐에서 추출한 curCost가 더 큰 값이라는 이야기이다. 이 경우 해당 간선을 이용하지 않을 때 더 작은 cost가 들기 때문에 해당 경우는 무시해준다.

 

가장 작은 간선을 뽑아냈으면 그 간선으로 간 노드에서 갈 수 있는 간선들을 다시 비교해본다.

 

`d[curIdx] + nxtCost < d[nxtIdx]` 인 경우 해당 간선을 이용하면 더 짧은 경로가 되는 것이다. 해당 간선을 이용한게 더 짧다면 간선을 이용해 다음 노드로 간 더 짧아진 길이로 최단거리 테이블을 갱신하고, 우선순위 큐에 그 노드를 넣는다. 

 

이 방법을 우선순위 큐가 빌 때 까지 반복하면 최단경로 테이블을 완성할 수 있다.