다익스트라 알고리즘

다익스트라 알고리즘이란, 가중치가 음수가 아닌 그래프에서 임의의 한 노드로부터 다른 모든 노드들로의 최소 거리를 구하는 알고리즘입니다.

알고리즘의 각 단계는 다음과 같습니다.

출발 노드 : K,  
노드 a 에서 노드 b 까지 거리 : distance[a][b]  

1. 각 노드로의 최소 거리를 저장할 배열 dist를 만들고, 값을 INF로 초기화 시킵니다. dist[K]의 경우 0을 저장합니다.
    (INF란 해당 타입이 지원하는 가장 큰 값, 또는 단순히 매우 큰 값입니다.)
2. 현재 노드 K와 연결된 다른 임의의 노드 N이 있을 경우, dist[N]의 값과 dist[K] + distance[K][N]의 값을 비교하여, 후자의 값이 더 작을 경우, dist[K]의 값을 dist[K] + distance[K][N]로 업데이트 합니다.
3. 현재 노드 K와 연결된 모든 노드들에 대하여 단계 2를 수행합니다.
4. 현재 노드 K와 연결된 노드들 중 거리가 가장 짧은 노드로 이동하여 단계 2 ~ 3을 진행합니다. 
5. 모든 노드를 방문할 때까지 이를 진행합니다. 

예시

다음과 같은 임의의 방향 그래프가 있습니다. 노드 1로부터 다른 노드들로의 최소 거리를 구해보도록 하곘습니다.

현재 노드 1과 연결된 노드가 2와 3이 있습니다. 여기서 이 두 노드로의 최소 거리를 구해보도록 하겠습니다.
먼저 현재 노드 1에 대하여 연결된 각 노드에 대해 다음의 비교를 진행해 줍니다. 예를 들어 노드 2의 경우,
dist$[2]$(현재 저장된 노드 2로의 최소거리) 와, 노드 1까지의 최소거리와 노드 1부터 노드 2까지의 거리의 합 ( dist$[1]$ + distance$[1][2]$ ) 을 비교합니다.
지금의 경우, dist$[2]$ 는 INF 의 값을 가지고 있기 때문에, dist$[1]$ + distance$[1][2]$ ( 0 + 2 = 2 ) 의 값으로 업데이트 됩니다.
노드 3도 마찬가지로 dist$[3]$ (INF) > dist$[1]$ (0) + distance$[1][3]$ ( 3 ) 이므로 dist$[3]$의 값도 3으로 업데이트 됩니다.

이제 노드 1과 연결된 노드 2로 이동하여 같은 단계를 반복합니다.
노드 2와 연결된 노드 3에 대하여, 노드 1에서 노드 3으로 가는 거리가 더 짧은지, 아니면 노드 1에서 노드 2를 거쳐 노드 3으로 가는 거리 더 짧은지 확인합니다.
dist$[3]$ (3) 의 값과 dist$[2]$ (2) + distance$[2][3]$ (4) 를 비교했을 때, 전자의 값이 더 작으므로, dist$[3]$의 값은 그대로 유지됩니다.
노드 2와 연결된 노드 4의 경우, dist$[4]$의 값은 INF로 저장되어 있어, dist$[2]$ (2) + distance$[2][4]$ (5) 의 값이 저장됩니다.

노드 3으로 이동하여 똑같이 수행합니다.
기존에 저장된 dist$[2]$의 값과 현재 노드 3을 거쳐 노드 2로 가는 것 중 어느 것으 더 짧은지 비교합니다.
dist$[2]$ (2) < dist$[3]$ (3) + distance$[3][2]$ (4)의 값을 비교하였을 때, 전자의 값이 더 작으므로, dist$[2]$의 값은 유지됩니다.
다음으로 연결된 노드 4와도 비교하는데,
dist$[4]$ (7) 의 값과 dist$[3]$ (3) + distance$[3][4]$ (6) 의 값 중 전자의 값이 더 작으므로, dist$[4]$의 값은 그대로 유지됩니다.
최종적으로 각 노드로의 최소 거리는 다음과 같습니다.

p. 1753 최단경로

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

제가 다익스트라 알고리즘을 알게 해준 아주 고마운 문제입니다….
보통 다익스트라 알고리즘을 구현할 때 자주 사용되는 것이 우선순위 큐 입니다.
기존의 그래프 탐색 방법인 bfs와 비슷하게, 방문한 노드를 큐에 저장하여 탐색을 진행합니다.
그러나 조금 다른 점은 우선순위 큐에 각 노드와의 거리를 -기호를 붙여 음수의 형태로 저장합니다. 그렇게 될 경우, 절댓값이 가장 작은 값, 즉 가장 거리가 짧은 노드가 우선순위 큐의 top에 위치하게 되어, 그래프 탐색을 진행합니다.
코드는 다음과 같습니다.

Code

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 20001
#define INF 210000000
int V,E,K;
vector<pair<int,int>> graph[MAX];
priority_queue<pair<int, int>> pq;
int _min[MAX];
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> V >> E >> K;
    while(E--){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v,w});
    }
    for(int i = 1; i <= V; i++) _min[i] = INF; 
    pq.push({0, K}), _min[K] = 0;
    while(!pq.empty()){
        int cur = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();
        for(int i = 0; i < graph[cur].size(); i++){
            int next = graph[cur][i].first;
            int nextDistance = graph[cur][i].second;
            if(_min[next] > distance + nextDistance)
                _min[next] = distance + nextDistance, pq.push({-_min[next], next});
        }
    }
    for(int i = 1; i <= V; i++){
        if(_min[i] == INF) cout << "INF" << '\n';
        else cout << _min[i] << '\n';
    }
}

사실 이 문제는 제가 굉장히 애를 썼던 문제였습니다. 처음 봤을 때는 쉬운 문제겠구나 싶었는데, 생각보다 어떻게 해야할 지 애를 먹었습니다… 그러던 중 다익스트라 알고리즘을 알게 되었고, 간단히 풀 수 있었습니다…

p. 1916 최소비용 구하기

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

위의 p. 1753 최단경로 문제와 같은 문제입니다. 여기서 다른 점은 위의 문제는 모든 노드로의 최소 경로를 구했다면, 이 문제는 특정 노드로의 최소 경로를 구하면 되는 문제입니다. 코드는 다음과 같습니다.

Code

#include<iostream>
#include<vector>
#include<queue>
#define MAX 1001
#define INF 210000000
using namespace std;

int N, M, start, _end;
vector<pair<int, int>> buses[MAX];
priority_queue<pair<int, int>> pq;
int smallest[MAX];
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M;
    while(M--){
        int cost;
        cin >> start >> _end >> cost;
        buses[start].push_back({_end, cost});
    }
    for(int i = 1; i <= N; i++)
        smallest[i] = INF;
    cin >> start >> _end;
    pq.push({0, start}), smallest[start] = 0;
    while(!pq.empty()){
        int cur = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        if(cost > smallest[cur]) continue;
        for(int i = 0; i < buses[cur].size(); i++){
            int next = buses[cur][i].first;
            int nextCost = buses[cur][i].second;
            if(smallest[next] > nextCost + cost)
                smallest[next] = nextCost + cost, pq.push({-smallest[next], next});
        }
    }
    cout << smallest[_end];
    return 0;
}