[C++] 다익스트라(Dijkstra)

핵심 요약

• 최단 경로 탐색 알고리즘.
• 방문한 노드들과 연결된 간선 중 최소 비용인 간선을 선택하는 알고리즘.
• 단, 가중치가 양수일때만 적용할 수 있다.

 

동작 원리

1. '비용' 이라는 말을 많이 사용하게 될 텐데, 이 값은 1차원 배열 Dist[] 라는 배열에 저장되어 있다고 생각하자. 초기 Dist배열의 모든 값은 무한대(INF)로 초기화 되어 있다.
2. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.
3. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 체크해준다.
4. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.
5. 3 ~ 4번 과정을 반복한다.

 

구현

1. 비용을 저장할 int형 배열

2. 간선을 저장할 pair<int, int>를 자료형으로 하는 vector 배열

3. 최단 경로를 탐색하기 위한 우선순위 큐

 

아래는 백준 1916 최소비용 구하기의 코드이다.

다익스트라 알고리즘을 사용하는 기본적인 문제이므로 코드를 보고 이해해보자.

https://www.acmicpc.net/problem/1916

 

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

int n, m;
vector <pair<int, int>> v[1005];
int dist[1005];

void dijkstra(int start){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    dist[start] = 0;

    while(!pq.empty()){
        int dx = pq.top().second; 
        int cost = pq.top().first; //현재 도시까지의 비용
        pq.pop();

        //if(기록된 비용 < 현재 도시까지의 비용) 스킵.
        if(dist[dx] < cost) continue; 

        for(int i = 0; i < v[dx].size(); i++){
            int nx = v[dx][i].first;
            int nCost = v[dx][i].second;

            if(cost + nCost < dist[nx]){
                dist[nx] = cost + nCost;
                pq.push({dist[nx], nx});
            }
        }
    }
}

int main(void){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int start, end, cost;
        cin>>start>>end>>cost;

        v[start].push_back({end, cost});
    }

    for(int i = 0; i <= n; i++){
        dist[i] = INF;
    }

    int start, end;
    cin>>start>>end;

    dijkstra(start);

    cout<<dist[end];
    return 0;
}