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

다익스트라 알고리즘 (Dijkstra Algorithm) : 하나의 정점에서 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다. 기본적인 아이디어는 아래와 같다.

1. 각 노드의 최소 길이와 각 노드 간의 거리를 담는 배열을 생성해준다. 노드의 최소 경로의 길이를 담는 배열은 dist[5], 각 노드 간의 거리를 담는 배열은 path[5][5]라고 정하겠다. 이 때, 시작점(1) -> 시작점(1)의 거리는 0이고 (dist[1] = 0), 시작점(1)에서 아직 출발하지 않았으므로 (1)에서 각 노드까지의 거리를 INF로 초기화해준다.

1	2	3	4	5
0	INF	INF	INF	INF

2. (1) -> (2)와 (1) -> (3)을 거리를 구해보자. 경로는 각각 (1) -> (2), (1) -> (3)이다.

(1) -> (2) : dist[2] = min(dist[2], dist[1] + path[1][2]) = min(INF, 5) --> dist[2] = 5
(1) -> (3) : dist[3] = min(dist[3], dist[3] + path[1][3]) = min(INF, 2) --> dist[3] = 2

1	2	3	4	5
0	INF	INF	INF	INF
	5	2

3. (1) -> (4)의 거리를 구해보자. 경로는 (1) -> (2) -> (4) 또는 (1) -> (3) -> (4) 둘 중 하나이다.

(1) -> (2) -> (4) : dist[4] = min(dist[4], dist[2] + path[2][4]) = min(INF, 5 + 6) --> dist[4] = 11
(1) -> (3) -> (4) : dist[4] = min(dist[4], dist[3] + path[3][4]) = min(11, 2 + 4) --> dist[4] = 6

1	2	3	4	5
0	INF	INF	INF	INF
0	5	2	INF	INF
0	5	2	6	INF

4. (1) -> (5)의 거리를 구해보자. 경로는 (1) -> (2) -> (5) 또는 (1) -> (3) -> (5) 또는 (1) -> (3) -> (4) -> (5) 이다. (3번의 과정으로 (1) -> (3) -> (4)가 (1) -> (2) -> (4)보다 짧다는 것을 알아냈고, 그 정보를 dist[4]에 저장해놓았다.)

(1) -> (2) -> (5) : dist[5] = min(dist[5], dist[2] + path[2][5]) = min(INF, 5 + 3) --> dist[5] = 8
(1) -> (3) -> (5) : dist[5] = min(dist[5], dist[3] + path[3][5]) = min(8, 2 + 1) --> dist[5] = 3
(1) -> (3) -> (4) -> (5) : dist[5] = min(dist[5], dist[4] + path[5][6]) = min(3, 6 + 7) --> dist[5] = 3

1	2	3	4	5
0	INF	INF	INF	INF
0	5	2	INF	INF
0	5	2	6	INF
0	5	2	6	3

개념은 위와 같고, 이제 백준의 [1753. 최단경로]를 풀어보자.

1753. 최단경로

문제

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

풀이

다익스트라 알고리즘을 이용해서 푸는 방법이다. 일반적인 방법으로 풀면 안되고, (vector에 넣고 전부 탐색하게 하면 시간초과가 난다.) 우선순위 큐에 정점 번호의 최단 거리를 쌍으로 묶어서 저장하고, 우선순위 큐가 빌 때까지 계속 탐색해준다. 위의 문제에 나와있는 예시를 이요해서 좀 더 구체적으로 말하자면,

우선순위 큐에 시작 노드인 1과 1번의 최단경로인 0을 묶어서 넣어준다.
top의 첫번째 값을 d(최단 거리), 두번째 값을 n(노드 번호) 라고 하자.
d > dist[n]이면 그냥 빼버린다. dist[n]은 해당 노드까지 오는 경로 중에서 가장 짧은 경로를 저장한 값이며 d는 이전 노드가 어떤 노드인진 모르지만, 이전 노드에서 n번 노드까지의 거리를 의미한다. 후자가 전자보다 작다는 보장은 없으므로 비교를 해줘야한다.
d가 최단 경로가 될 때, n번 노드 -> 인접 노드의 거리가 dist[인접노드 번호] 보다 작으면, dist[인접노드 번호]를 업데이트 해준다.
이 결과를 거리 정보를 음수로 치환해서 우선순위 큐에 다시 넣어준다.

여기서 음수로 치환하는게 어떤 의미냐하면, 음수를 우선순위 큐에 넣으면 절대값이 작은게 먼저 나올 것이다. 즉 시작 노드에서 가장 짧은 거리를 가진 노드부터 탐색한다는 얘기가 되며, 이는 시작점에서 가장 최단 거리에 있는 인접 노드부터 탐색해야하는 다익스트라 알고리즘과 같다. 만약 이 제어를 걸어주지 않게 된다면, 가령

1 : <2, 2> <3, 3>
2 : <3, 4> <4, 5>
3 : <4 ,5> ...

를 가질 때, 1번 검색이 끝나면 맨처음 꺼내게 되는 것은 <3, 3>이 되어버리며, 이는 다익스트라 알고리즘의 과정과는 다르게 된다.
이 문제에 관한 좀 더 자세한 이야기는 아래 링크를 통해 확인해보자.

https://www.acmicpc.net/board/view/34516

소스코드


//
//  1753.cpp
//  test
//
//  Created by 신기열 on 03/07/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <utility>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

const int INF = 2e9;

vector<vector<pair<int, int> > > adj; // (u,v,w) -> adj[u] =  ... :: u -> v 거리가 w임.
int n, m, start;

void Dijkstra(int s){
    
    vector dist(n + 1, INF);
    priority_queue<pair<int, int> > pq; // 노드 거리, 노드 번호 순으로 저장해 줌
    dist[s] = 0; pq.push(make_pair(0, s)); // 시작점 저장
    
    while(!pq.empty()){
        
        int d = -pq.top().first, n = pq.top().second; pq.pop();
        
        // 이전 노드에서 현재 노드까지의 거리가 최단거리에 해당한다면 현재 노드의 인접 노드들을 전부 탐색해준다.
        // d는 이전노드에서 n번노드까지의 거리를 나타내므로, d가 dist[n]보다 크면 시작점부터 n번의 이전 노드까지의 거리가 뭐가 나오든 무조건 dist[n]보다 크게 된다.
        // 물론 d = dist[n]은 시작점부터 탐색할 경우 가능한 얘기이므로 d가 dist[n]을 넘지만 않으면 된다.
        if(d <= dist[n]){
            for(int i = 0; i < adj[n].size(); i++){
                int v = adj[n][i].first, w = adj[n][i].second;
                
                // 현재노드에서 인접노드까지의 거리가 인접노드가 저장하고 있던 최단경로보다 작으면 업데이트 해주고, 우선순위 큐에 그 정보를 저장해준다.

                if(dist[v] > dist[n] + w){
                    dist[v] = dist[n] + w;
                    pq.push(make_pair(-dist[v], v));
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(dist[i] == INF) cout << "INF" << '\n';
        else cout << dist[i] << '\n';
    }
}

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    cin >> start;
    adj.resize(n + 1);
    
    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
    }
    
    Dijkstra(start);
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Dijkstra/1753.cpp

Cat On The Keyboard

이 블로그 검색

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

댓글

댓글 쓰기